A couple suggestions off the top of my head:
what does explain show for your queries? For count(*) in particular it should be able to use any unique index and not read each actual block of the table. For the first query I think you are out of luck since the string concatenations will make the optimizer throw up its hands and give up.
Is there a way you can get distinct rows in the first query without actually using distinct? I can see how sorting 2M rows might be hard on the DB.
does the count(*) improve after you run it a second time, i.e. after presumably the data is already in memory?
what options are you starting postmaster with? The defaults suck.
As to the bug in the first query, all I can think of is that they definitely fix bugs between versions; maybe you should upgrade. :)
