Hi,
Sounds like you're starving for power. On the spec page for the Mega it says it needs 6V-20V at the limits (http://arduino.cc/en/Main/ArduinoBoardMega2560) so I'm thinking if your wall wart is 5V as you've typed, it's struggling to power your circuit.
Cheers !
Geoff