If the payment details entered work ok elsewhere, in iTunes say... then presumably there's an issue with app store or supporting files; although we've covered most all of the per-user ones, and you find problems in a new account too.
You could temporarily try the certificate settings detailed here - although a new/guest account has those set to off already, when checking here - so that's likely a bust.
Does Console - All messages show anything when attempting to buy something in a new admin account ?
Can you use the app store in the Guest user ?
If replacing/updating the app store didn't work - it seems that something else is missing/damaged & that reinstalling/updating OS X after backing up is a next step. If you already have the combo update & latest security update downloaded - try both of those first.
*edit* - did I or anyone ask earlier if you had any security software installed ? - sometimes that can cause problems.