What you're describing really sounds like a firewall problem. Rather than disabling the Ubuntu firewall, you might just want to add the necessary ports to the exceptions list because disabling the Ubuntu firewall might just cause the system to default back to a "default drop" firewall rule which would be obviously unhelpful.
As an easy diagnostic you can type "iptables -S" into a terminal with administrative privileges (i.e. as root or with sudo) to see what your existing firewall rules are. If there's a "-P INPUT DROP" in the list then its dropping all incoming packets that don't match a rule, which means your firewall is very much not disabled.
The ports you need to exempt are 1900 (UDP and TCP), and 52000-52999 (UDP and TCP), but you can see more specific ports by looking under the media network report view under the "Services & Plugins" tree view. That view will also show you if you've successfully enabled media network and the status of MC's media servers.