Congratulations! I know how it feels too. What a relief. You're doing a fantastic job and rebuilding!
I was able to settle on a large credit card debt (90 days late) for about 40-45% of the original balance. It wasn't charged off yet, so I have "settled for less than full amount" on my credit report, which I can live with. I think my FICO went up about 70 points. In my case, it was the amount of debt just as much as the utilization that was holding my score down. Not long after the settlement, I started getting a few modest credit card approvals (and then a wonderful Discover It unsecured card a scant three months after the settlement!).
I still have to learn patience, but when I look back, it's amazing how quickly things have started to look up. I mean, I'm still not "there" yet, but it's such a difference from about 10 months ago. An amazing difference.
Edit: I should add that I still have some more debt I'm paying off, on some cards that were never delinquent. I was able to get on a 5-year payment plan with the bank with low interest (and the cards are closed). This keeps my utilization way up. But even with that, it's still amazing how things have improved.