I am running QGIS 2.10 on Linux Mint 17.2 (based on trusty), and in the Heatmap plugin the available formats dropdown is not empty, so your problem is not a general problem with QGIS running on LM/Ubuntu. I'm not sure how to reproduce this problem.
However, you suggest that the issue arose after an update to 2.10. It occurs to me that a significant amount of QGIS functionality (esp. for plugins) is dependent upon python-qgis. This could explain the difference between Heatmap (plugin) and Raster Calculator (which I believe is core), so I would check that you have python-qgis that installed with
apt-cache policy python-qgis
and install it if it is missing.
Another concern is that you say that you updated to 2.10 from the ubuntugis-unstable PPA. However, as far as I can tell, ubuntugis-unstable only goes up to version 2.8. Not sure why this would lead to incomplete functionality. Maybe you have QGIS 2.10 but python-qgis 2.8? The discrepancy does imply that you may not have installed from the repository that you intended.
If you are running Ubuntu Trusty, I would recommend installing 2.10 from the QGIS repository, but begin by purging your current installation:
sudo apt-get purge qgis python-qgis
Then add the following lines to /etc/apt/sources.list:
deb http://qgis.org/ubuntugis trusty main deb-src http://qgis.org/ubuntugis trusty main
Note: although you can edit /etc/apt/sources.list directly, in practice I prefer to use the Software Sources tool (available standalone or from the Synaptic menu) to add new repository source lines.
After doing that, update and reinstall qgis and python-qgis packages via Synaptic or:
sudo apt-get update sudo apt-get install qgis python-qgis qgis-plugin-grass
These instructions taken from http://qgis.org/en/site/forusers/alldownloads.html#debian-ubuntu. I can also confirm that they work, as that is how I got QGIS 2.10 installed on LM 17.2. This is also the instructions for the version designed to work with ubuntugis dependencies, and requires the use of the ubuntugis-unstable PPA, which you are already using. But if you are using a more recent Ubuntu release than Trusty, you have to pick the appropriate version, and not use ubuntugis dependencies. Check the link for further instructions.
Raster→Heatmap→Heatmap…menu). The dialog allowed me to select the format. Can you provide more information or a screenshot, because I can't confirm your issue.