Ahhh I wonder if that is the problem then. I had a user in New Zealand too that couldn't find any of them. There is an app provided by SlideME | Android Community and Application Marketplace
and you can get a home launcher from them or from GetJar - Appsolutely Everything for Nokia, BlackBerry, Android, Samsung, Sony Ericsson, LG, Palm.
. Both of these you access via your web browser on your phone and then download their app which is bit like the Android market. They don't have as many apps avaiable but it might be a way to get things that aren't available through the market.