Is there a tool like Hamachi (https://secure.logmein.com/US/products/hamachi2) which works on ubuntu? Bonus points if it can be paired with something running on windows/mac.
OpenVPN is the server and client side program that does the communication, and there are a number of GUI tools for configuring OpenVPN to do pretty much everything that Hamachi2 does:
Here's a good list:
I don't use any of them, but they all should be safe to try out for sure.