Ahh the good old boy problem... yea I ran into that as well that year I was in Texas, US. Mainly due to my age and flamboyance (They didn't like the head of of their CERT team (yea yea I realize it's redundant, kinda like PIN Number) having purple highlights in his hair).
As for your situation, it sounds like you're still in some sort of schooling? If so I'd look into getting any sort of retail job that involves computers or electronics. Not sure what the Australian equivalent is, but even something like Best Buy's Geek Squad or a small computer store would be good.
What this does is puts you in the work force, and as it's always said, it's easier to find a job you want when you already have a job. Also when you're in the interview and asked why you were working at such a low job compared to your qualifications it's simple to say "Well I was taking classes still and I need a job, any job while I looked for 'this one'".
Employers tend to shy away from candidates with large gaps in their work history.
Additionally I'd recommend learning all you can about the Cisco IOS. It's a great place to start and most places will expect any sort of network security professional to know networking and cisco systems inside and out... after that pick a single product line and start focusing on that. You can either pickup the books at your local library, used copies online, or even ebooks and PDF's (Legal or illegal. Yes I'm saying pirate the books to get into the field, because I guarantee you they'll get your money after you're working in the field (you don't want to know how many shelves of technical books I've purchased once I started working in the field)). Don't expect your classes to cover what you'll need to learn.
Finally... be willing to get out of that town. Accept an offer to relocate from a company. It sounds like that city is not a good place for you. And, that's something I understand all too well.
There you go, a bit of advice from someone that was once in that situation. Take it or leave it. If there's anything else I can help with let me know. :)