Have you tried selecting your store view on the system configuration page?
Sometimes that value is overriding the "default" value.
Have you checked the "Allowed Countries" configuration?
I have some questions:
Can you please tell me how did you resolve this. I am having the same problem but I cannot make it work in any possible way.