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' ))
[DateOfCallis 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