David Blasby <dblasby@refractions.net> writes:
> I have a table with about 16,000,000 rows in it.
> When I do a:

> SELECT * FROM <table> LIMIT 1;

> it takes about 10 minutes (thats about how long it takes to do a full 
> sequential scan).

The only explanation that comes to mind is huge amounts of dead space
before the first live row.  But the output of "vacuum verbose" would
probably be enough to tell whether this is really the correct diagnosis.

> I had originally thought that there might be a large number of 
> "wasted/retired" tuples in the table so I "vacuum analysed" the 
> database.  It had no effect.

It wouldn't; you'd need vacuum full to collapse out the dead space.
You could also try CLUSTER which is faster than VACUUM FULL when most
of the data has to be moved anyway.  (Some days I think we should dump
VACUUM FULL, because it's optimized for a case that's no longer very
interesting...)
        regards, tom lane