I asked about Colette last week; you can see some replies there.
http://www.behindthename.com/bb/arcview.php?id=3655777&board=baby
I prefer Colette to Nicolette; it is enough of a name in its own right. I like it because it is not seen very often (usually, at least around me), but it is still easily recognizable.