I use Ubuntu 16.04.4 x64 and have a problem with Ubuntu software center. It doesn't find some programs (for example teamviewer) even more: software center doesn't find any program that's already installed
Remove Software Center:
sudo apt-get remove software-center --purge. Then re-install it:
sudo apt-get install software-center. You now should find a new-look Software Center that works OK. You will find it from File Manager in Computer/usr/share/applications, where you can drag the icon to the Launcher Bar.