Is a clustered index on column A the same as creating a table ordered by A?
Like @dezso commented, creating a new table and dropping the old used to be faster in old versions, but not any more with the new implementation in pg 9.1.

The most common problem with CLUSTER is that it requires an exclusive lock on the table, which does not go well with concurrent access to it.

The solution to this problem is pg_repack, which does not lock the table exclusively.

Generally, make sure that your server configuration is fit for the task. High settings (a lot of RAM) for maintenance_work_mem would help both CLUSTER and CREATE INDEX on big tables. Standard setting is way too small for you. Follow the links for details.

You might set it very high temporarily for a transaction with SET LOCAL and leave it at a reasonable setting otherwise:

BEGIN;
SET LOCAL maintenance_work_mem = ????MB; -- find the sweet spot
CLUSTER tbl;
COMMIT;


If possible, set it high enough to fit the whole operation in RAM.

More:


PostgreSQL 9.0 how to reclaim disk space after delete without rebuilding table?
Configuring PostgreSQL for read performance