Extremely slow performance with 'select *' after insert of 37,000 records

The table in question is a simple users table.  The details are at the
bottom of this message.  The performance on this table was fine during
testing with less than 100 users.  Then we inserted about 37,000 records
into the table.  Now a 'SELECT * FROM pp_users' takes over 40 seconds!!.
  37,000 records is not much at all so I am wondering why the slow
execution time.  Here are some stats and log output files.

Running the query 'SELECT * FROM pp_users'
------------------------------------------
On LAN connection (using pgadmin):
   Total query runtime: 14547 ms.
   Data retrieval runtime: 10453 ms.
   37326 rows retrieved.
On Internet connection (using pgadmin):
   Total query runtime: 32703 ms.
   Data retrieval runtime: 16109 ms.
   37326 rows retrieved.
On db server using psql (somewhat better but still slow for 37000 rows):
   devel=# select * from pp_users;
   Time: 912.779 ms

Running the query 'EXPLAIN ANALYZE SELECT * FROM pp_users'
-----------------------------------------------------------
   "Seq Scan on pp_users  (cost=0.00..1597.26 rows=37326 width=1102)
(actual time=0.029..33.043 rows=37326 loops=1)"
   "Total runtime: 44.344 ms"
(same stats when run on all computers (lan/internet/localhost)

Anybody know what would cause things to be so slow?  Seems kind of
absurd really.  Indexes shouldn't play a role since a 'select *' does a
sequential scan.  Even so there will be an index on the primary key
(user_id) which is proved with the query:
   EXPLAIN ANALYZE SELECT * FROM pp_users WHERE user_id < 100
   "Index Scan using pp_users_pkey on pp_users  (cost=0.00..7.80 rows=4
width=1102) (actual time=0.080..0.246 rows=54 loops=1)"
   "  Index Cond: (user_id < 100)"

Let me know if any more information would help.  This is postgresql
7.4.7 (also a unicode database).

Regards,
Collin

---------------------
-- Table: pp_users

-- DROP TABLE pp_users;

CREATE TABLE pp_users
(
   user_id serial NOT NULL,
   title varchar(10),
   firstname varchar(40) NOT NULL,
   lastname varchar(40) NOT NULL,
   shortname varchar(20) NOT NULL,
   username varchar(20),
   "password" varchar(40) NOT NULL,
   birthdate date,
   sex char(1),
   weight int4,
   company varchar(40),
   email varchar(60),
   tel1 varchar(40),
   tel2 varchar(40),
   fax varchar(40),
   street varchar(40),
   city varchar(40),
   zipcode varchar(10),
   state varchar(30),
   country varchar(40),
   "language" varchar(5),
   cellphone varchar(40),
   userstatus_id int4 NOT NULL DEFAULT 1,
   acc_deleteme varchar(4),
   proxy text,
   settings text,
   creationdate date DEFAULT now(),
   createdby_user_id int4,
   div1 varchar(40),
   div2 varchar(40),
   div3 varchar(40),
   div4 varchar(40),
   role_id int4,
   joined_date date DEFAULT now(),
   membership_id varchar(40),
   password_status int4,
   CONSTRAINT pp_users_pkey PRIMARY KEY (user_id),
   CONSTRAINT "$3" FOREIGN KEY (userstatus_id) REFERENCES userstatuses
(userstatus_id) ON UPDATE RESTRICT ON DELETE RESTRICT,
   CONSTRAINT role_id_fk FOREIGN KEY (role_id) REFERENCES pp_roles
(role_id) ON UPDATE RESTRICT ON DELETE RESTRICT
)
WITH OIDS;