Try putting better antennae on the router? If it can't accept external antennae, try getting one like the ASUS RT-N12 (I love it; I've owned 3 and they all still work, I sold one to a buddy and I use two).
Make sure firmware is up to date.
IIRC, WPA2 encryption basically is a lot harder to transmit / receive than the useless WEP, a lot of cheap routers or routers near the edge of connectivity seem to have this issue.
Oh, be sure that if any system using the router has Windows XP, that it's updated to SP3, as SP2 on down do not support WPA2 natively (the crappy add-on connectivity software does, however, I avoid those like the plague).