So are you actually using WPS to set up the connection?
I have never bothered with this and just key the password into the device when connecting and it "just works"!
I have Android 4.0.4, my daughter has 3.x.x (can't remember the exact version and my wife has the GingerDX flavour of Cyanoganmod - all connect to at least three routers without problems.
Ex <n>ildram , been to SKY MAX - 15,225 Download
BE Unlimited - 21,000 Download 1,200 Upload,
Moved house, now BE Unlimited 6,500 Down, 1Mb/s up - gutted!
FTTC Cab installation commenced 12th April - expect full 80 / 20 - bye bye BE, hello BT Infinity soon!