Slow queries on big table

I have a two column table with over 160 million rows in it. As the size
of the table grows queries on this table get exponentially slower. I am
using version 8.1.5 32-bit on Red Hat Enterprise Linux 3. The hardware
is an Intel 3 Ghz Xeon with 4GB RAM, and 6 disks in a RAID 5
configuration. For current testing I am running a single database
connection with no other applications running on the machine, and the
swap is not being used at all.

Here is the table definition:

mdsdb=# \d backup_location
Table "public.backup_location"
Column | Type | Modifiers
-----------+---------+-----------
record_id | bigint | not null
backup_id | integer | not null
Indexes:
"backup_location_pkey" PRIMARY KEY, btree (record_id, backup_id)
"backup_location_rid" btree (record_id)
Foreign-key constraints:
"backup_location_bfk" FOREIGN KEY (backup_id) REFERENCES
backups(backup_id) ON DELETE CASCADE

Here is the table size:

mdsdb=# select count(*) from backup_location;
count
-----------
162101296
(1 row)

And here is a simple query on this table that takes nearly 20 minutes to
return less then 3000 rows. I ran an analyze immediately before I ran
this query:

mdsdb=# explain analyze select record_id from backup_location where
backup_id = 1070;

QUERY PLAN

------------------------------------------------------------------------
------------------------------------------------------------------------
-------------
Index Scan using backup_location_pkey on backup_location
(cost=0.00..1475268.53 rows=412394 width=8) (actual
time=3318.057..1196723.915 rows=2752 loops=1)
Index Cond: (backup_id = 1070)
Total runtime: 1196725.617 ms
(3 rows)

Obviously at this point the application is not usable. If possible we
would like to grow this table to the 3-5 billion row range, but I don't
know if that is realistic.

Any guidance would be greatly appreciated.

Thanks,
Ed