Connection drops out regularly with a Ralink RT2800

I actually have the same card so I know where you're coming from. I haven't had any issues surprisingly, as I did in the past.

My suggestion would be to try compiling the compat-wireless drivers from source. You can download from: Linux Wireless - Stable
I recommend using compat-wireless-3.5.4-1-snpc

sudo apt-get install linux-headers-$(uname -r) build-essential
tar jvxf compat-wireless-3.5.4-1-snpc.tar.bz2
cd compat-wireless-3.5.4-1-snpc
./scripts/driver-select rt2x00
make
sudo make install

Then do a reboot.

If that doesn't work I'd try updating the kernel to the latest. I'm on 3.2.0.31.34 without any problems, and I did not need to compile the drivers.

sudo apt-get update
sudo apt-get dist-upgrade
sudo reboot now

Have you disabled network-manager after installing wicd?

service network-manager stop 

Since if two managers control the same interface, it will likely to disconnect very often.

Also I have seen possibly similar problem described in ArchLinux wiki:

If dmesg says wlan0: deauthenticating from MAC by local choice (reason=3) and you lose your wifi connection, it is likely that you have a bit too agressive powersaving on your wifi card

I had exactly the same problem with this device. What I found was that making it use 5GHz is rock solid stable (I have an SSID that is 5GHz only). If I let it use 2.4 GHz then it works for a short while before becoming unreliable, and then eventually stops working completely.

Added for RolandiXor: If you have an access point that has both 2.4 and 5Ghz and it lets you set separate SSIDs on each band then you can have an SSID that is present on the 5GHz band only, and set the computer to use that SSID which means it will be doing 5GHz only.