Windows 8 Store: Your Purchase Couldn’t be Completed

I've been struggling with this problem - I try to install a free windows 8 store app like trello and it just tells me that a problem occurred and my purchase couldn't be completed.

After googling around and finding a few solutions, none of which worked, I noticed that I had disabled the windows update service (I don't recall doing that but, hey). Enabling and starting the windows update service and magically the windows store worked again.