Help with performance and explain.

I have an issue with a select returning very slowly  approx 198 seconds. 
I took a backup of this DB and restored it on another system and it is 
returning in 28 seconds.

Windows 2000  PG Version 8.0.3  Data is inserted into the table row by row.
Table has index on service
explain SELECT   callrecord."service", callrecord."timequeuing", 
callrecord."timeconversation", callrecord."timeoffering", 
callrecord."calltype", callrecord."application"
FROM   "public"."callrecord" callrecord
ORDER BY   callrecord."service" ASC

"Sort  (cost=284032.83..284322.17 rows=115734 width=46)"
"  Sort Key: service"
"  ->  Seq Scan on callrecord  (cost=0.00..270144.34 rows=115734 width=46)"


Windows 2000 Version 8.0.1  DB created from backup of other server.
explain SELECT   callrecord."service", callrecord."timequeuing", 
callrecord."timeconversation", callrecord."timeoffering", 
callrecord."calltype", callrecord."application"
FROM   "public"."callrecord" callrecord
ORDER BY   callrecord."service" ASC
"Sort  (cost=17465.33..17754.65 rows=115729 width=46)"
"  Sort Key: service"
"  ->  Seq Scan on callrecord  (cost=0.00..3577.29 rows=115729 width=46)"

Any help would be greatly appreciated.

Oisin