I don't have much info on disks, since this is a virtual server on linode. It is running ubuntu 12.04, 8cpus, 4GB ram, 95GB ext3 volume (noatime). Hopefully that's helpful.
Bryce
Well, did you run benchmarks? How many IOPS do you get from the volumes?
Try running "iostat -x -m -d 10" while the slow query is running and pasting the results (or a relevant sample of them).
Also, do run "explain (analyze, buffers)" instead of plain "explain analyze".