How about writing to director of the sevice center.

And call CIS again. Some people on www.immigration.com dicussion board posted the trick to get a person in the sevice center (second tier customer service) instead of contracted operator.May be this help.
If none of above works, contact senator and congressman in your state