You will still have the warning message there even though you have indexed a column. As long as you have indexed all of the columns you would potentially need to filter on then you should be fine.
The warning is there to let you know that you will soon hit the threshold and that if you want to filter on any fields they need to be indexed before you hit that threshold. I would say you and the warning worked exactly as intended.
If you really wanted to get rid of the warning you could raise the list view threshold, but it's not generally recommended. In your case it doesn't really seem needed either.
EDIT:
Here's some more documentation on the list view threshold and a quote pulled directly from the article.
Manage lists and libraries with many items
To give you time to make alternative plans, SharePoint 2010 warns you on the List Settings page when your list has exceeded 3,000 items. The warning contains a help link to this topic.