When you upload an extension, Joomla creates a temporary copy in tmp directory. Then it moves it to where it should be. So if it can't find it or isn't allowed to copy from it, you get the error message.
Conditions that have to be met.
1. There must actually be a tmp folder
2. The path to the tmp folder must be correct in Global Configuration. (see screenshot for where to find this in Global Configuration)
3. The tmp folder must be readable and write-able. Permissions set to 755 at least.
Here are some other references that will be helpful if the quick fix doesn't work for you