Most of the time this is due to permalinks.
In order to modify permalinks, a module called mod_rewrite is used to frame URLs of individual posts/pages/ categories in your WP blog.
WordPress doesn't work fabulously out of the box with IIS as it does with Apache (which does have mod_rewrirte).
Follow the instructions here and see if your host is running at least the bare minimums, if not the latest version of PHP and to check the specs of your server.
The thing is Apache supports "mod_rewrite" but IIS doesn't. And Linux hosting almost always uses Apache as the web server whereas WIndows based hosting will use the built-in IIS web server.
These links *might* help your provider to better configure the IIS service to work with WP.
=====================
Other people have had limited success by modifying "wp-includes/wp-db.php" with the code located here. Try this @ your own risk or perhaps venture to the WP support forums
http://www.php.net/manual/en/install.iis.php
http://bugs.php.net/bug.php?id=25863