Yeah, seriously, wtf? I have had many "first time callers" to my phone and never saw it proclaimed on screen as such. Does it show this in lieu of the number, like it would if you had a name programmed? Or, somewhere else on the screen in small text? Do you have the skype app installed? I noticed it has some interesting hooks into the call system on the phone, maybe it's messing with the caller id recognition somehow.
Could it be from SkyDeck? Google Sync? Back-Up Assistant?
I dont use any of those applications...if I had to guess it would be back up assistanct since that deals directly with your contact list. Maybe someone will pop up with the same problem soon....