To answer your question, give it time, your hands will toughen. As Glenn said, the straps are normally used to save the hands. I, personally, always use straps on my heavier pulls for that reason. No grip problem here.
Glenn and Greg,
Very related question to this thread.
How tight should one grip the bar when pulling with a hook grip? I find when I just get a nice hook and don't think about my grip, things go better. As a oppossed to really getting a good gorilla grip on the bar like when I'm getting ready to pull a very heavy strapless deadlift.
I'm curious as to your thoughts on this.
All the best,