Local Tile Server - EXTREMELY slow rendering

I have my own tile server on Oracle Linux. My rendering is extremely slow. I rendered an 8x8 Z16 metatile that took 124 minutes to complete. Foreground Renderd put out:

renderd[5601]: DEBUG: Got incoming connection, fd 8, number 1
renderd[5601]: DEBUG: Got command RenderPrio fd(8) xml(default), z(16), x(17723), y(25170)
renderd[5601]: DEBUG: Connection 0, fd 8 closed, now 0 left
renderd[5601]: DEBUG: DONE TILE default 16 17720-17727 25168-25175 in 7474.548 seconds
debug: Creating and writing a metatile to /var/lib/mod_tile/default/16/0/70/82/53/128.meta

I have some PostgreSQL log statements on the order of 300,000 ms as in:

2013-07-15 18:31:04 EDT:::1(33790):user@osm_planet:[5610]:LOG:  duration: 340648.541 ms  execute <unnamed>: SELECT ST_AsBinary("way") AS geom,"amenity","ele","landuse","leisure","man_made","military","name","natural","place","point","shop","tourism","waterway" FROM (select way,aeroway,shop,access,amenity,leisure,landuse,man_made,"natural",place,tourism,NULL as ele,name,ref,military,waterway,historic,'no'::text as point
               from planet_osm_polygon
               where amenity is not null
                  or shop in ('supermarket','bakery','clothes','fashion','convenience','doityourself','hairdresser','department_store', 'butcher','car','car_repair','bicycle')
                  or leisure is not null
                  or landuse is not null
                  or tourism is not null
                  or "natural" is not null
                  or man_made in ('lighthouse','windmill')
                  or place='island'
                  or military='danger_area'
                  or historic in ('memorial','archaeological_site')
              ) as text WHERE "way" && ST_SetSRID('BOX3D(-9202100.961200738 4642173.601817815,-9196597.495164203 4647677.067854352)'::box3d, 900913)

2013-07-15 18:36:25 EDT:::1(33790):user@osm_planet:[5610]:LOG:  duration: 320782.717 ms  execute <unnamed>: SELECT ST_AsBinary("way") AS geom,"name","way_area" FROM (select way,way_area,name
               from planet_osm_polygon
               where name is not null
                 and (waterway is null or waterway != 'riverbank')
                 and place is null
               order by way_area desc
              ) as text WHERE "way" && ST_SetSRID('BOX3D(-9202100.961200738 4642173.601817815,-9196597.495164203 4647677.067854352)'::box3d, 900913)

2013-07-15 18:41:49 EDT:::1(33790):user@osm_planet:[5610]:LOG:  duration: 324224.378 ms  execute <unnamed>: SELECT ST_AsBinary("way") AS geom FROM (select way,way_area,name,boundary from planet_osm_polygon where boundary='national_park' and building is null) as boundary WHERE "way" && ST_SetSRID('BOX3D(-9202100.961200738 4642173.601817815,-9196597.495164203 4647677.067854352)'::box3d, 900913)

I am using Mapnik 2.1.0, PostgreSQL 9.2, PostGIS 2. I have a 16GB instance in my company's virtual environment.

I tried adjusting my postgres.conf settings with pg_tune, but no luck. Something must be really wrong for 1 metatile to take 2 hours to render LOL. Any thoughts at all????

In Response to Frederik's answer: I think you nailed it. On my sick tile server I ran EXPLAIN and got back:

Seq Scan on planet_osm_polygon  (cost=0.00..6997002.90 rows=2 width=362)
   Filter: ((way && '010300002031BF0D0001000000050000000D28C29E368D61C1DE2E84665FB551410D28C29E368D61C1C8B95744BFBA51419962D8AF868A61C1C8B95744BFBA51419962D8AF868A61C1DE2E84665FB551410D28C29E368D61C1DE2E84665FB55141'::geometry) AND ((ame
nity IS NOT NULL) OR (shop = ANY ('{supermarket,bakery,clothes,fashion,convenience,doityourself,hairdresser,department_store,butcher,car,car_repair,bicycle}'::text[])) OR (leisure IS NOT NULL) OR (landuse IS NOT NULL) OR (tourism IS NOT
NULL) OR ("natural" IS NOT NULL) OR (man_made = ANY ('{lighthouse,windmill}'::text[])) OR (place = 'island'::text) OR (military = 'danger_area'::text) OR (historic = ANY ('{memorial,archaeological_site}'::text[]))))
(2 rows)

On a different tile server that is working better I ran the same query and got back:

 Index Scan using planet_osm_polygon_index on planet_osm_polygon  (cost=0.00..9.44 rows=1 width=1133)
   Index Cond: (way && '010300002031BF0D0001000000050000000D28C29E368D61C1DE2E84665FB551410D28C29E368D61C1C8B95744BFBA51419962D8AF868A61C1C8B95744BFBA51419962D8AF868A61C1DE2E84665FB551410D28C29E368D61C1DE2E84665FB55141'::geometry)
   Filter: ((amenity IS NOT NULL) OR (shop = ANY ('{supermarket,bakery,clothes,fashion,convenience,doityourself,hairdresser,department_store,butcher,car,car_repair,bicycle}'::text[])) OR (leisure IS NOT NULL) OR (landuse IS NOT NULL) OR
(tourism IS NOT NULL) OR ("natural" IS NOT NULL) OR (man_made = ANY ('{lighthouse,windmill}'::text[])) OR (place = 'island'::text) OR (military = 'danger_area'::text) OR (historic = ANY ('{memorial,archaeological_site}'::text[])))
(3 rows)

To my untrained eyes, this looks like my indexes are messed up on the slow server? Here is the exact osm2pgsql statement I ran, do you see anything wrong with it? Or do you think something just got arbitrarily messed up during the import and I should just try again?

time /tiles/osm2pgsql/osm2pgsql-master/osm2pgsql -S /tiles/osm2pgsql/osm2pgsql-master/default.style --flat-nodes /tiles/flat --number-processes 4 --cache-strategy dense --slim -d osm_planet -C 8192 /tiles/planet-1304121/planet-latest.osm.pbf