probably a silly question... but are you including all the correct long distance extensions and area codes in the number you've given him?
Yeah, UK mobile phone numbers are seriously confusing. Make sure you're giving him the complete, correct number - with the international prefix and the country code and all and make sure he's using it. I may be wrong, but I think for the US to the UK it will start 011 44. Your mobile may list its own number as including the +44 country code so you don't need that a second time.