This sounds gross...

Trim a green onion and let her chomp on that. My mom swore by that.

It's an old wive's rememdy, but it works.

http://www.naturesnaturalhealing.com/Teething.shtml