Maybe something's screwy in the database. Go download and enable the Devel module, and in the settings turn on "Collect query info" and "Display query log". Next, go to the catalog page that shows the pager, and look for "pager_query" in the long list at the bottom.

It should be there twice. Take the SQL next to them and run it directly on your database. I want to see what results they get. One should be a bunch of information about the products in the catalog, and the other should give you the number of rows returned by the first query. Should be. It sounds like they're not for some reason.

By the way, are you using PostgreSQL?