Update 2013-02-08: It seems that this error is triggered by many different conditions. If you have my problem, the following steps may help you. If not, please don’t post “this didn’t help, any ideas?” I cannot help you further. If you have new information to add, please do post a comment!
Recently Google offered a sale on 10 Android apps each day for 10p (or 10¢). During the sale I bought a number of apps, because 10p is practically indistinguishable from “free”. Unfortunately, my bank believed this large number of sub-one-pound purchases to be fraudulent. Normally they’d be right; that’s exactly the kind of thing criminal organisations do when testing credit cards. But in my case, it was just a case of “SALE! SALE! SALE!” madness.
I cleared it with the bank, but after that I could no longer buy applications through the Android Market application. When I attempted to do so, the Market required me to check “I agree to the Payments for Android
Market Terms and Conditions”, then failed with the message “Error while retrieving information from server.”