The old reindexing tool has been retired as we moved into Tridion 2013. In this new version, there are many commands that can be executed via PowerShell scripts, including a command to reindex search in the CME.
Initially, I just ran Sync-TcmSearchIndex. This command did absolutely nothing in my case. Found out there's a way to query the database by going thru each publication one-by-one.
(Get-TcmRepository).ID | Sync-TcmSearchIndex -verbose
Search finally worked again after executing the above command!