Right off I just want to say it sucks when the error message is correct but you don't understand why.
We needed to add a new payment method to a Commerce Server 2007 implementation. The Customer and Orders UI threw an error immediately when going to manage Payment methods:
The underlying table was full of data. The site has been in production for over a year, collecting credit card payments the whole time without issues. Obviously the payment methods weren't missing.
Of course, Googling was no help whatsoever. I played with the Commerce API, wrote some code, ran SQL traces, all to no avail.
So on the a non-production version of the site (with the same problem luckily), I decided to work on the database table directly. I scripted off the original data, and truncated the table. Now the UI doesn't throw the error. So I re-added the data manually, and again the UI is fine, no errors.
So I compared the newly entered data with the old data, and there was a difference (outside of the obvious differences like keys). There is a bit column in the table called IsDefault. In the old data, all rows except one were set to False. In the new data, all rows were set to True. To test that this was the problem, I truncated the table again, and re-inserted the original data. Then I changed the IsDefault values to True on all the rows. Bingo. The UI now works again, and I could add the new data. So apparently someone did modify the data in the past, and the error message was correct about the database being tampered with. Luckily this modification had not affected Commerce Server's ability to process credit cards.
I think the IsDefault column refers to the language setting for the row in the table, as you can have multiple language variants for a credit card and choose which one is the default language. So for the UI to function properly, at least one row for each language needs to have IsDefault set to True.