The UK prefix is 44, no 0. It replaces the lead zero of the STD code.
So if the number is 01234 5678910 the "international" version would be + 44 1234 5678910
The calls are failing because of the spurious 0 after the 44. As for where that 0 is coming from (or indeed the +44) that is another matter.
I have a HTC Desire and if you go into Settings > Call > Phone Settings > Home Dialing there is an option to add the Country Code to the number. But if you believe the box where this is set it strips the lead zero off. However I haven't used it so can't say for sure what that setting does. But if there is a similar setting on your phone it might be worth checking.