Well there are two methods that are a guaranteed fix on most people's phone but there is another 3rd method.
Method 1. Go to your Menu button > Settings > Applications > Manage applications > Press All > and then scroll down to Market. Press clear cache first and then clear data second. If you clear data it will clear cache but the first way is my method. Reopen the market.
Method 2. Try LCD Density and set it back to the regular density if you have custom rom.
Method 3. A Godsend which is marketEnabler in the market. Download it and fake your provider as Verizon and reopen the market. I've provided more in-depth instructions below...