Just obtained a USB NextG Telstra wireless broadband modem. It has been activated and runs on XP, but on Linux Mint it asks for authentication.

The message says
'passwords or encryption keys are required to access the wireless network Telstra.' the box the shows Wireless security, with options for WEP 128-bit passphase,or WEP40/128 bit key.
Under that is a box for the key, which I dont know.

Has anyone used telstra USB wireless broad band on Linux Mint and can you advise whether it is compatible and or if there is a solution

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.