permalinks and .htaccess

I would like to change the permalinks from default to “pretty” but (of course) when I do, I get page not found on all the links to my entries. (I want to utlize tantanoodle’s flickr gallery plugin)

From everything I read on this site, it appears I need to access .htaccess to make changes in order for the changes of permalink to work. However, I can find NO WAY to access this file on my site. When I contacted my server, their response: Kindly note that your domain is hosted on a windows servers and we do not support all the functions of the ‘.htaccess’ file on it.

Any suggestions outside of changing hosts? I am running WP 2.0.1; if I upgrade might I be able to change these permalinks without having to access the .htaccess file?

Thanks – any help would be appreciated.