Haha! Fixed!

I pretty much followed what egyember did and its now working just fine!
I did however go a step further and small things like this irritate me. I removed US from the country list.

I have a suspision that not all of the above steps are required to fixed the problem.
Egyember, did you at any point go to admin/store/settings/store/edit and just press 'Save configuration' without changing anything? I didnt :S Perhaps thats all that was required?

Thanks guys! Your input is greatly appreciated.