Sounds like a possible loose or corroded connection, or possibly a temperature control issue. Start by checking in the water heater compartment where the power comes into the element. Look for loose connections, or corrosion. If you have and know how to use an multi-meter you can check for power and make sure it is getting all it needs.
Another odd thing to check for is; do you have another high draw item like a fireplace? Sometimes they will "split" a circuit between two high draw items and have a shut down solenoid to keep you from powering both of them up at once.
Aaron