Simple Join

I'll just start by warning that I'm new-ish to postgresql.

I'm running 8.1 installed from source on a Debian Sarge server. I have a
simple query that I believe I've placed the indexes correctly for, and I
still end up with a seq scan. It makes sense, kinda, but it should be able
to use the index to gather the right values. I do have a production set of
data inserted into the tables, so this is running realistically:

dli=# explain analyze SELECT ordered_products.product_id
dli-# FROM to_ship, ordered_products
dli-# WHERE to_ship.ordered_product_id = ordered_products.id AND
dli-# ordered_products.paid = TRUE AND
dli-# ordered_products.suspended_sub = FALSE;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=5126.19..31528.40 rows=20591 width=8) (actual
time=6517.438..25123.115 rows=14367 loops=1)
Hash Cond: ("outer".ordered_product_id = "inner".id)
-> Seq Scan on to_ship (cost=0.00..11529.12 rows=611612 width=8) (actual
time=393.206..15711.715 rows=611612 loops=1)
-> Hash (cost=4954.79..4954.79 rows=21759 width=16) (actual
time=6076.153..6076.153 rows=18042 loops=1)
-> Index Scan using paid_index on ordered_products
(cost=0.00..4954.79 rows=21759 width=16) (actual time=136.472..5966.275
rows=18042 loops=1)
Index Cond: (paid = true)
Filter: (paid AND (NOT suspended_sub))
Total runtime: 25136.190 ms
(8 rows)

This is running on just about the world's slowest server (with a laptop hard
drive to boot), but how can I avoid the seq scan, or in general speed up this
query?

to_ship will have far less tuples than ordered_products, but it's still not
small, as you can see.