For power, I'm using an LP2950 3.3v. I'm using a separate LP2950 5v to power the arduino and LCD. The 3.3v rail only powers the radio.
Short answer, yes, I've tried radios both with and without the capacitor.
Funny thing though... with my power arrangement, the power from the USB adapter provides the 5v rail, but not the 3.3v rail. Your answer made me think about that.
So, I tried both the radio with the capacitor, and plugging in my external power supply. But never did both together. In this application, the external power was necessary to power the 3.3v rail, and the capacitor was also necessary.
Thanks so much for guiding my thoughts in the right direction!
To clear up any ambiguities: The capacitor was the key to solving this problem. That and the external power. The project now works as expected (minus any debugging I might still need to do).