This seems to be the case. I have tried the very same thing with the same card. Once like every 20 times I do ifup I can see the SSID, and when I do see it it is practically impossible to connect due to packet loss and latency.
I updated the kernel to 3.6.6 and compiled hostapd 1.0.
No improvement.
https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1032826
(Update: I bought a TL-WDN4800 instead. No problems at all. Got it working in just a couple of minutes using hostapd 0.7.3 and kernel 3.6.6.)