Thanks to some googling, I found what appears to be a foolproof way to fix broken market links in Android. This typically happens after flashing a new ROM and restoring your apps via some backup tool like Titanium Backup.
Open titanium backup
go to Market
Click it and clear the data.
Now go to menu > Market Doctor and follow those steps to repair.
Go to your market and accept the disclosure.
Menu > My apps.