I'd try something other than Ubuntu (or grab another desktop environment, Unity is pretty horrible)
Anything that follows freedesktop standards should llow you to create an application launcher by placing a file in /usr/share/applications with the extension .desktop - this definitely works in Cinnamon and Gnome, and probably Unity since it's forked from Gnome as well. (Cinnamon is really nice, by the way)
Write a shell script called minecraft.sh or something, including the text "java -jar /path/to/minecraft.jar", and save it somewhere you remember. cd to the directory you saved it and run chmod a+x minecraft.sh (chmod changes file permissions, a+x is execute). Create your .desktop file - there's some documentation here:
http://stackoverflow.com/questions/12964512/creating-an-application-launcher-for-gnome-3-in-ubuntu - should work in Unity. For the execute path, put the path to your .sh, and put the path to any square png icon in the icon. Then, restart your computer if it's not already in the menu and you should have an application launcher.
I never had any issues in Fedora, it should be pretty easy.