I have found the problem/issue that may cause this problem
Over at http://www.ire.org/extraextra/ we are moving to WordPress from an older version of Moveable Type in the process of building a new website and we had this similar problem. On Moveable Type we had around 2,200 posts which we imported into WordPress. Once the posts were imported, we found that our permalink structures at first would not work. This was solved when we allowed our apache server to write to the .htaccess file. Furthermore, after the server problem was fixed, our permalinks on archived pages would only work when we were logged in as administrators. After logging out of the wordpress admin area, our permalinks in regards to individual page posts and archive pages, would show a "post not found" or a "not here" where the post should normally go.
The problem was that the importing script within WordPress does not actually publish the posts when they are imported. It tries to publish them, and will show inside of the MySQL databases that they are published, but within WordPress, they are not actually published. MT to WordPress has one specific problem:
The (wordpress) php page that imports moveable type to be "Published" has a capitol P, rather than a lowercase p in its script. This sounds funny, but after causing four hours of confusion this was found to be the complete cause of all of our problems. Running a command to turn all of the “Publish” texts within our server into “publish” with a lowercase p instantly published all of our posts, and the permalinks worked thereafter. This is with the latest version of wordpress as of 6/28/08.
The people who wrote the MT to wordpress script for wordpress have a capitalization issue to fix.
I really hope this helps you guys, moving from MT to WordPress can be a pain. Also if you don’t have direct access to your apache server there are other posts regarding how to make .htaccess rewritable by other methods.
Good luck if you're having this problem,