There are two parts to what the shuffle's light is telling you.
The flashing part means Do Not Disconnect. If you Eject the iPod (using the small button next to the shuffle in iTunes) and leave it connected, it should no longer flash. So flashing or not flashing is not related to the battery or charging.
The red part means the battery level is currently very low. If it does not change to amber (and green), that means the battery is not charging normally.
Make sure you have a good USB connection. If you are connecting it to a USB hub (instead of a direct connection to the computer), it may not be receiving enough power to charge. Also, too many USB devices connected at the same time can overload the computer's USB bus, so if there are other USB devices connected to the computer, try it with everything else disconnected (except for standard keyboard and mouse).
You can also try doing a Restore in iTunes. Select the shuffle in the iTunes sidebar, under DEVICES. Over to the right, go to the Summary tab. The Restore button is there. This will erase the shuffle, re-install its software, and set it to default settings. If a software or settings glitch is causing this problem, a Restore should fix it.