SELECT * FROM <table> LIMIT 1; is really slow

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).

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. I had a "vacuum full" going on the table
for 17 hours before I killed it.

Any idea why its so slow? It used to be instant.

dave