Ok, I've scoured the community forums for answers to my issue and I haven't seen any so I thought I'd throw this out there to see what everyone thought:
First, a little context: I currently have scores in the high 500s, although I don't have any collections or judgments on my report, I have three 30 day late payments (1 from Nordstrom and 2 from Capital One that they REFUSE to remove. With Capital One, I changed the due date on my account and there was some confusion on my part as to when the payment was due (on the old due date or the new one I set up). They have since waived the late fees but refuse to remove it from my report, even after I have written several GW letters, no dice) and my debt utilization is pretty high (like 90% high), but other than that I have had a sparkling payment history and have never been late, and my credit history is pretty solid. I think the debt utilization and the 3 late pays are somehow killing me.
So I recently paid off my Citi Thank You card from a balance of $415 to $0 ($500 CL), paid down my Chase Freedom card from a balance of about $1800 to a balance of about $600 ($2000 CL), and my Nordstrom card from a balance of $450 to $350 ($500 CL). I haven't seen not one thing from any of the bureaus indicating any sort of bump in my score (myFICO is showing that the accounts have been updated but that's it), yet the balance for my Capital One Quicksilver card increased by $12 and my scores have gone down by between 8-10 points for all of the bureaus, AND my credit utilization is now being reported at 99%. 
It's like I took two steps forward (paying down balances) and 4 steps back (FICO score went down instead of up). Very frustrating.
Any thoughts, ideas, words of encouragement?
Thanks!
TBH just keep paying down your utilization. The darned near close to optimal FICO candy land is typically one card reporting a small balance. There's some oddities that people have reported, they don't make a lot of sense with the conventional wisdom but there's tons of reasons to pay off the CC debt and none not to for both FICO and the more important financial rationale.
How long ago were those 30 day lates?
Also something sounds strange from your description, try signing up for Credit Karma and look at the tradelines in more detail than what you get here at MF, possible something got lost in translation in the presentation... though the scores here are as good as you'll fine anywhere, whereas CK's really aren't and some of their interface stats should be utterly ignored (like what it counts for account age).
