I Read the OP yesterday and whilst I normally pay by card, I thought I would try by the phone bill method to test.

Once I selected payment by phone, Nokia Store just hung with a circle of death. After ten minutes I closed the Nokia Store app.

Now I am experiencing exactly the same problem as described in the OP. I use T-Mobile UK so I think it if the store and not a carrier specific problem.

I will email Nokia store support and see what they recommend.