Site with large number of posts

I have a site that has around 17,000 custom post type entries in it. They all have an average amount of custom post data (they are POI’s, with address, coordinates, etc). Nothing out of the ordinary, just using the built-in CPT’s and postmeta. However, now that I have that amount of posts, the ?edit.php?post_type=blah does not even pull up. Neither does the Add New Blah screen. When I click on the Add New or All Blah’s, it just loads…and loads.

Am I doing something wrong? Do I just need better hardware?
I know this is all very vague; a better question may be – what requirements has anyone in a similar situation had to require to support such a number of posts? This site is currently on a mid-range VPS, along with ~100 other sites.