Can you please upgrade to the latest stable version, 1.7.2 and see if you still have problems?
This may not be this, but due to list volume, we're limited in supporting older versions here.
You might also enjoy "accelerated mode" though this doesn't really help you with an individually slow step, I suspect there's something wrong with what the setup module is doing.
on the local machine, can you checkout ansible (devel branch is fine), and try:
source ./hacking/env-setup
./hacking/test-module -m setup
This will allow you to run the setup module locally and if need be, run it with some debug breakpoints or printouts added to see where it's holding up. (Unfortunately some development familiarity is required)
Perhaps it's not a thing on 1.7.2 regardless, so I'd try that first.
Thanks!