I had a similar problem in France this year. You are quite correct as a PM account it does come as standard but my issue was the same as yours(i travel a lot and havent had an issue until France this year) and the issue was that an international call bar that prevents you calling numbers in country and outside of your phone book was in place. It's apparantly a deeply hidden call bar that not all CS representitives know about.
I only became aware of it as I needed to call some in country numbers and it flaged up then.
