It should be compatible. I say "should" because I know its worked in a fashion for a few years with the drivers in the kernel, its just required some low-level fiddling to get it going (search for "quozl maxxon" on Google if all else fails).
However, from 9.10, Ubuntu had a wizard that detected it, and asks which carrier you are with (Telstra, Optus etc). I mention this because of Mint's heritage (Ubuntu-based). Not sure what version of Mint you are running (you might get more help if you are a bit more specific about what you are running - Mint version, KDE/Gnome etc., post some output from "lsusb" and "lsmod"). Getting the device going with the inbuilt desktop (Wizard) support would be preferable, as its then managed by NetworkManager and you don't need to dive to the command line just to start the connection.
You shouldn't be getting asked about WEP/WPA -that's generally for wireless LAN, not the 3G modem.
An side on the password - interestingly, when directly configured using ppp and the kernel modules (a la Quozl) you didn't need the Telstra credentials to get access, it recognised the SIM. With the Ubuntu Wizard, it should ask you for your Telstra/BigPound account and password.