Have you run this update query again and again with vacuuming?
http://www.postgresql.org/docs/7.4/static/maintenance.html#ROUTINE-VACUUMING
If so, you might have millions and millions of dead tuples taking up
space and slowing things down. If you're running 7.4, install the
autovacuum daemon and turn it on. Nice little program that should mostly
take care of this issue for you.
Got any foreign keys on that field? Triggers?
