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