Performance w/ multiple WHERE clauses

I am running into a serious performance issue with some basic queries.

If I run something like

select * from "Calls" WHERE
( ("CallType" = 'LONG DIST' ))

The search takes about 15 seconds

if I run
select * from "Calls" WHERE
( ( "DateOfCall"='06/19/02') )
AND ( ( "CallType" = 'LONG DIST' ))
[DateOfCall is a DateTime field]

it takes 15 minutes!

both columns are indexed individually and expalain reports and Index scan for both
queries.

Any pointers where to look next?

Running pg 7.2 on RH

Thanks,
-Aaron Held