There was an issue with the store. Several folks reported the same issue so I tried it with an 8.1 device I had and experienced the same issue. It took a couple of days for them to fix it but it worked fine last night and today it appears as if it is working even better.
So it was not your device but an outside issue which should be resolved now.