I do not think it is a bug, but some apps can take a very long time to be indexed by spotlight, especially if you have a lot of apps set to be indexed in this manner. It's possible that spotlight froze somehow and simply never got round to indexing your contacts.
What I did was to turn off every app that I knew I would need to be searched , leaving only a few core apps to be searched and indexed by spotlight.
Here's an example of my settings. I have about 56 apps indexed, out of over 100 apps installed. You can probably get that number way down if you are more selective.
That should help speed up your contacts being indexed by spotlight.