As I answered to Tom few moments ago:
>reducing 'random_page_cost' from 2 to 1 and increasing 'effective_cache_size' from 70% to 80% of RAM solved this at least on my virtual sandbox.
I've observed same behaviour both on weak virtual machine and on the quite powerfull stress test platform.
The first one is Ubuntu 12.04 LTS, second one is RedHat 6.4
Of course, RAM. RAID, CPUs and so on are different enough, so I believe the root clause of this issue is not connected with hardware at all.
Thanks for your idea with external sort, I'll test it