Hi,
I verified that I'm having the same problem with a couple of Mega's - the RF24 works fine when connect it to the Mega2560 and I power it from an Uno, but not when it's powered from the Mega directly. I would not have found that without your post, so thanks for that!
Azar3 - you said "Next I removed the extra nano voltage supply and put a Tantalum capacitor 4.5uF across the mega's 3.3v and it worked fine." Can you elaborate? Where does the capacitor go exactly - between the Mega's 3.3v and gnd?
Also, I measured the voltage output from the mega's 3.3 pin with a multimeter, and was surprised to see that it was a completely steady 3.30 volts. I guess there's something wrong with the voltage that doesn't get picked up by the multimeter?
Remko