I've just had the Watch for a few hours and tried the phone app right away - it failed on two different numbers. I've been trying to find out what I might be doing wrong - perhaps some setting on the iPhone?
But I'm patient and having a blast messing around with it all.