you can also try this. from the home screen press the menu key > settings > applications > manage applications > select the all tab at the top > wait for all the app icons to load > scroll down till you find market and select it > tap on clear data. This will wipe your market back like it was before the first time you used it. You'll notice that the next time you open up the market app you will have to accept the terms and conditions. It may still be on the old market, mine was. So, i just downloaded an app. I backed out of the app market and let the app install. The next time I opened up the app market it was on the newer style. This seems to be about the most common thing I find when trying to get the market to update.
ps. I sell verizon phones. So i see this almost everyday. Hope it helps!
Chad