I finally found a way to fix this after my 2nd Galaxy Nexus in 2 months wouldn't charge (Verizon replaced the first one because of this issue, then I figured they wouldn't be so generous the second time around).
The charger may appear to insert fine into the female micro USB port, but the "lightning bolt" won't appear to show it is charging if the "tongue" inside the female receptor (a flat metal bar the length of a piece of rice) is bent. This bar should be exactly in the middle of the receptor. If it is pressed down even a little bit, the charger will insert smoothly but it won't connect and charge.
Here is what you do:
1) remove the battery (for safety)
2) insert a small object (flathead jewelers screwdriver or a small nail) below the metal bar and gently push it up
3) reinsert the battery and it should charge
Be careful you don't break the bar or you'll void your warranty. When my first Galaxy Nexus wouldn't charge, the Verizon store employees looked it over, couldn't figure out what the problem was, and authorized a new phone. That's probably your best bet the first time this happens.