This fix is quite simple, and doesn't require uninstallation of the Market update every time it reinstalls itself.
1. Go to Settings >> Applications >> Manage applications >> All.
2. Scroll down and click on Market.
3. Click on the "Clear data" button.
4. Using whatever method you favor, change the LCD density to 160 for now.
5. Reboot your device.
6. Go to the Market and click the Accept button when prompted.
7. Go back and change the LCD density back to whatever you like.
8. Reboot your device.
Done! The Market should now work properly