btw, what's the version of db ? what's the work_mem setting ?
try setting work_mem to higher value. As postgresql will fallback to disc sorting if the content doesn't fit in work_mem, which it probably doesn't (8.4+ show the memory usage for sorting, which your explain doesn't have).