PostgreSQL and most modern, ACID-compliant RDBMSes use MVCC instead of locks. MVCC has a lot of upsides, namely, you almost never need table-level locking for writes, but it ensures you need to look at the whole table to do COUNT. That's because MVCC is basically multiple parallel universes for data. What you see depends critically on which transaction you're in when you look.
For example, suppose you have a process that needs to know the number of users in some user table. You start your transaction, and then another process starts a transaction that goes through and deletes certain users. While this is happening, you need the count. In MVCC, deletion doesn't delete, it just marks rows with the transaction ID range in which they're visible. The rows that are being deleted by the other process are just being marked dead as of that process's transaction ID, but your transaction ID is below that one, so they're not dead to you. Later on, when the youngest transaction alive is older than the oldest transaction that can see these rows, PostgreSQL will actually expunge the data (VACUUM does this).
Because of MVCC, there is more than one legitimate answer the question of COUNT; potentially, one for each transaction in progress. The answer is changing constantly. People tend not to think in these terms; we tend to think, well the table has so many rows in it, right? Why don't you just increment the count when you write one? It's not true, because with ACID compliance, uncommitted transactions should not have visible effects until they commit and transactions in progress should not see anything vary during their operation. So there really are multiple right answers at any given moment. The expectation that SELECT COUNT(*) will be fast is built on the assumption that the database has some sort of master count of what rows are in the table it can just glance at. But it doesn't, and to have one would require removing MVCC altogether and using locks instead.