So far, the only solution I found was to drop the database.
Connect to the postgres database:
psql postgres (Note: you cannot be connected to the database you want to drop)
Drop the database
DROP DATABASE databasename;
Quit postgres
\q
Restart the Odoo server with ./odoo-bin and open localhost:8069 in your browser. Odoo will ask you to create a new database.
Now, this solution worked for me as I just installed Odoo and had only the sample data yet. But for anyone who has live data in the database, a better solution might be recommended.
Update:
A better solution is to make sure you have the Database Cleanup module installed be installing/uninstalling apps. You can see it with this tutorial here.
Assuming that you still have the error occurring, go to Settings > General Settings > Database cleanup > Purge obsolete tables
Click on the Select lines button.
Check the “mail_compose_message” line and click on Purge in the Action drop-down.
This should fix the issue. You should now be able to install new apps.