It may be possible to play M:tG on Ubuntu for free via the advice in this link.
From a quick glance over them, none of the programs in the link seem to natively support Linux/Ubuntu. It may be possible to use these applications via WINE/Play On Linux.
An alternative to going through a Windows application and using WINE/POL is Cockatrice which seems to use .deb packages so should be fairly simple to setup. The problem is - the official website appears to be down currently (as of 27th of February 2013) for legal reasons. If you check this link you may find out more.
The final alternative is to use a platform such as Roll20. The Roll20 platform is built with table-top games in mind. In fact, I played a few DnD games on there with no issues. Because it's web based, there's no operating system compatibility issue, either. When I last used it, it only really supported Chrome, however.
Quick run through:
First method requires WINE.
Second method is down, but check the last link of that section!
Finally, with some major set-up you can do it via a web platform.
Hopefully one of these gives you an idea as to do!
Good luck!