Is this the same cable and/or charger you have always used? If it's the same charger and/or cable you have always used, I have no idea why it would start doing that all of a sudden. Maybe there is a chance the cable or charger has gone bad (if that is possible), I really don't know.
If it is a new or different cable and/or charger...I don't know how to fix it, but I have seen it happen w/certain chargers.
I have an old charger that worked on my original iPhone, and I get that same message on the iPhone 4 about not being compatible. Also, get that same message when trying to use one of those USB nightlight plugins. It will charge an old iPod touch, but not an iPad or newer iPod touch or iPhone 4. I think it has something to do with older chargers and newer versions of iPods/iPhones/iPads.
Also, I have a generic cable that will work on an old iPod touch but NOT the newer stuff.
I'll be watching this thread for sure to see if anybody knows of a fix.