When first trying to use the Windows Phone 7.5 Marketplace you might get the message "This might be because your phone software needs to be updated, the application is exclusive to a different mobile provider, or the app is not available in your region". Especially if you live outside of the US or UK.
To fix make sure your regional settings on the phone (Settings -> system -> region + language) are set to the same as your Windows Live ID that you are using for your phone.
Apparently you might also want to set region settings for Zune.net (I did not have to do this).
Read this on http://answers.microsoft.com/en-us/winphone/forum/wp7-sync/market-place-not-availavle-for-your-region-yet/74c7a9fd-34cd-4bd7-8349-59f07fcf923a#1a7f23cc-80ef-473a-9f94-e2d7fcac7379