I had this problem and I fixed it in minutes with no jailbreaking or software modifications. A small amount of water condensation from a cup holder in my car got into the dock connector port which caused this error message to pop up every few minutes, sometimes every few seconds, for about two weeks. I fixed it by cleaning the pins on the connector after reading the comments above. There may be a more professional way to do this, but I used what I had on hand and it worked.
1. Turn off the phone.
2. Fold a crisp, new $1 bill over two times, stick the folded corner under the pins and rub it back and forth quickly for approximately 30 seconds.
3. Fold the bill over one more time, stick the folded corner on top of the pins and rub it back and forth quickly for approximately 30 seconds.
4. Spray Windex on the corner of the bill, wipe off the excess with your fingers and repeat steps 1 and 2.
Notes:
I used the Windex because the dry cleaning did not fix the problem. I included information on the dry cleaning because it may be an important interim step.
I turned my phone off before starting this procedure, but it turned back on before I finished it. I might have turned it on accidentally or the Windex may have made a connection that caused this to happen. The lesson is make sure you don't use too much Windex. If your phone is new or if you aren't lazy like me you should probably go to RadioShack and get some contact cleaner.