Solved the issue, had WiFi on and suspected that might be the problem. Switch WiFi off, connected via cellular connection and the purchase went through.
PS This is NOT funny, but I had to laugh in any case, the purchase confirmation from Microsoft states "Purchase Date: 01 April 2014". Must've fallen into a time warp
I've got a U Choose Flexi contract, so the amount was deducted from my balance, quite a nifty way to use airtime when it builds up over a period of time. If your'e on prepaid, the amount will also be deducted, with other contracts the amount will be added to your account.
@grim: Seems correct, a Google search turned up similar issues with other providers. It will be interesting to know how shop app works with operator billing.