Hi there. It's possible you do not have a robots.txt page.
Just create one with a plain text editor and copy that suggested text into it.
FTP to your site and upload the file (you can also create this file by logging the shell and using vi)
That file should go into your domain root folder.
See if that straightens things out.
You mention this issue only occurring after a template change. Does this template have an admin panel associated with it? It's possible you need to set up the robot/indexing directives from within the template panel/WP dashboard.
See if the template developer offers some support.
One last thing:
Since you messed around with your htaccess file, in your WP dashboard, go to Settings > Permalinks and re-save/refresh.