Note To Self: Fixing broken market links on Android after wipe/ROM upgrade

Force stop market and clear data
Launch market again - it will ask you to accept terms. Do so.
Should force it to rebuild the database and you should see all your apps linked to market again.