I am getting 'Error 404 File Not Found' when I click on tags in Tags Cloud. However, tags are created properly.
What could be the issue? I do not have My Sites also so could that be a reason?
You need to have My Sites Host (you do not need to enable My Sites for all users) properly setup and configured.