I'm sorry to hear about your frustration and understand why you are upset. Keep in mind that paying off collections has no effect on your score, and if the collection had been dormant for a while and you paid it off, it could even hurt your score from bringing the reporting current and making it score like a new delinquent.
How delinquent were you on your student loans in 2004?
Having no revolving credit is hurting you a bunch. You need a mix of credit, and a lack of revolving credit makes companies very hesitant to lend to you. Try opening a secured credit card and maybe a store card to build some credit up. You need to show you can have revolving credit and be responsible with it.
With no mix of credit, serious derogatories, and your only trade lines show past delinquencies, it's not much of a surprise your score is so low. When you have negatives on your report, you aren't going to see much of a raise (if any) from removing other negatives because you are still in a dirty bucket.
Starting Score: 627 EQ, 621 TU - 11/15/08A 90 day past due is considered a key derogatory and is going to hurt your score until it falls off. Despite being current now, a 90 day late is just as bad as a charge-off in some respects. A good will letter cant hurt considering you are current now.
The fall off date is still based on the DOFD, but when a delinquent account that has been sitting for a while gets updated because of a dispute, recent activity, or a payoff, it makes the account look like a current delinquency. As with all negative items, with time the score effect begins to diminish, but making it recent will cause the original hit to show back up again.
For a secured card, try a local credit union. They are usually pretty lenient with their acceptance. If you search on the forums, there are a couple companies that will give you a secured credit card if you send them the minimum deposit.
There really isn't any recourse, and don't worry about the updated date. That won't hurt you. What sometimes happens is a charge off or collection reports as ok for a long time (despite being a negative account) and then all of a sudden you dispute or pay it off and it gets updated in a bad way.
You aren't truly shackled, just held back from certain things. Renting an apartment won't be that big of a deal; references and work history will help you there. Focus on getting a secured credit card first before you worry about an unsecured card. Baby steps.
Unfortunately this has happened to me too 
Get a secured CC as fast as you can. Since you have no revolving lines the baddies hurt more strongly. The single best thing to improve your score is getting a CC. Secured or not makes no difference in score but secured cards are easier to get and a few places don't even pull credit.
