Unknown problem with .htaccess

My host, Bloghosts, recently folded, and I moved my site over to BlogMoxie. The files were transferred by them, so whatever was in place on my old account made it over to my new account.
The problem is that my old rewrite rules no longer work to give “nice” URLs for permalinks. That is, the permalinks are what I want them to be, but clicking them results in a “Page not found” error.
I have searched these forums for insights, and I’ve even found some to try, but nothing seems to untangle my mess. Help!