I was in a similar situation not even a year ago. My score was in the higher 400's but still, very very low. I never thought it was going to change or get any better and I felt overwhelmed as I'm sure you do. I'm not sure what your age is, but I'm 27, and it's very embarassing to be in your twenties and have terrible credit.
One of the things I did was take advantage of a free credit counselor at my university. I didn't even know they had something like that. If you don't have access to someone like that through an educational institution, I suggest you look for one online and do your homework and make sure they are not a scammer. I want to say that the National Foundation for Credit Counseling has resources for referrals to free or low cost programs to help you with financial advice. The advice that I got from my counselor at the school was great and it helped me so I'll share it with you.
You can't just pretend your debt doesn't exist and hope it disappears. If you don't pay off those collections, you're not going to get out of the hole you're in. So she sat down with me and looked through my pile of collections letters and we decided to prioritize and to make sure the collection companies were indeed reputable companies and not just predators buying zombie debts over and over again. I was lucky that a few of my cards had their own collections departments (AMEX has their own collections department, as far as I know, they don't sell debt to collection companies like Portofolio or RJM) so we sat down and we made a list and I had to call and say I'm paying the full amount (not the settlement amount, the whole enchilada) and I did. I sent some places as little as $10-15 a month and I finally got about 50% of my collections debt taken care of. When I completed paying one account, I'd call up a new collections company to set up payment for the next. And it has taken me four years but I'm in the 600's now, steering towards the 700's hopefully there by fall 2014/winter 2015.
The next thing you want to do is get a secured credit card or a rebuilding card. I never had a secured card. I took out a student loan and this helped my credit score a bit and somehow it helped it enough for me to be able to qualify for a rebuilding card with a company I had never heard of--Merrick Bank. They sent me a nice little letter and I applied and I got the card with a $500 limit back in November 2012. It is now August 2013 and my Merrick card has a $1200 limit and they report each month about my timliness in payment history. That has helped BIG TIME. If you get your debts paid off, at least half or most, and you get your hands on a rebuilder or secured card that reports to ALL the credit bureaus, you will see a change in your score. But you have to be patient. I highly suggest that you find someone to mentor you as it helped me a lot.
Good luck to you! The most important thing is that you cannot be discouraged and do not be hard on yourself. You WILL see the light of day again. 
i had pathetic 500 score in Jan this year, then 550 by march, and couple of months ago I brought down my Util to less than 10%. Right now I am at 640+.
I have two paid collection, 6 other baddies, none of the prime banks won't give me any credit because it happend recently. (none of the baddies will fall of for 3-4 years, writing GW every month)
Good luck, you will see good score improvement once UTIL is low.
