I was hired on at a semiconductor company 2 months out of a technical school with an Associates in cns with a specialization in unix and my A+, Network+ and Linux+. The fact is, I completely expected to be running wires through attics for a few years before being able to work on the other side of a computer. It sounds like you have the same skills I stepped out of college with.
Back at the dorm I setup a PXE boot environment, which coincidentally is the same method kickstart uses to install a red hat machine. Having the keyword "PXE" in my resume and being able to walk the interviewer through the process step by step was what tipped the scales in my favor. The position was for a 3 month contract to re-image red hat desktops. That 3 month contract has been renewed continuously for 4 years now, and re-imaging is only a small part of what I do now.
You definitely need to start a lab at home with several dissimilar machines and OSes. Don't put a monitor on your server, make yourself do it all command line. Ditch windows if you really want to learn everything about linux. Don't use ubuntu, it's too easy. Use fedora or centOS, they're akin to Red Hat. Don't ever reboot your server, pull your hair out for 3 or 4 hours until you fix it without any downtime. Setup LDAP, setup active directory, setup a mysql db for your mp3 collection, figure out how to integrate that with Apache. Volunteer your computer skills at a church, even if it's helping someone setup gmail. Review a dozen resumes and make sure you put a "keywords" section at the bottom that includes acronyms that only a geek would know; a lot of companies parse through
resumes looking for keywords (pxe thank you).
Join your local LUG.
Be likable, read Dale Carnegie book: How To Win Friends and Influence People. I was hired on with another contractor of higher technical expertise, after 3 months they kept me and let him go. Why? I would sit with the manager and let him tell me about his kids, motorcycle, martial arts, asking questions and being genuinely interested. Most of all, learn how to deal with technically challenged users.
Setup your linked-in, it should be professional but it should show your personality too. In my linked in picture I'm holding a German Shepherd... every recruiter that contacts me now asks about the dog, and they remember me. Facebook should be very, very private even if there's nothing to hide. Recruiters sift through hundreds of these, so it's easy for them to skip to the next one.
I get all of my hits from linked-in and I'm in a town that's big, big, big, into the semiconductor industry and linux. If my location was Nebraska, I might not have as many hits as say... Austin, TX.