unfortunately counting on postgres is a heavy operation, and it's pretty "famous" for this http://wiki.postgresql.org/wiki/Slow_Counting......... maybe you can try limiting the amount to, let's say, 20000 (if it's possible as per requirements of your app) and see if there are differences.
In theory SELECT COUNT(*) from mytable and SELECT COUNT(*) from mytable LIMIT 20000 for a 500000 records table is faster. You could have a "default" grid of the 20000 records and then an "advanced" if users are willing to scroll over the n-thousand-x page.
