There are tons of jobs out there for people with linux skills. However, you have to start at the bottom - datacenter monkey, tech support, things of that nature. These jobs only pay 10 to 15 an hour, but you work one of those jobs for a few years, you will move up, build up experience, etc. If you are a talented person, then you will move up quickly.
I did this myself working at a datacenter, then eventually started working at a software company doing tech support - now i'm doing perl development. I started maybe 4 years ago, so this isn't impossible to do.
Most tech jobs that I look at require "degree or equivalent experience" meaning that as long as you can prove that you know what you are doing through work experience, then you should be fine. But you have to jump through the hoops of helldesk and crappy jobs first - not many people will hire you directly into a network administrator position if you don't show that you have a background in dealing with networks on a professional level.