count(*) is a linear time operation (roughly to the size of the table) on postgres. It does an index-only scan but with a sufficiently large table/index it's still a problem. It's to do with postgres MVCC implementation. I don't know if other SQL databases have this problem. MySQL doesn't seem to.
It's a problem in mysql too, unless you use an engine like myisam, which isn't realistic in most scenarios due to durability and concurrency concerns.