Do you have any credit cards currently reporting with a balance?
How many credit cards (visa, mc, discover, amex, store, gas) do you have?
You need to have a small balance on 1 card (just $10-20) in order to help your score. Remember that FICO is about risk to the lender. And if you DON'T use your credit, that is a risk....to profit. So FICO looks and grades that you have recent use of credit card (recent use means a reported balance).
When you paid the account, the creditor updated the report as PAID, but this also gave it a recently reported date, meaning that the late payment is more recent.
It would have been better to attempt to have done a Pay For Delete when paying an old account like that. It's hard to say how long it will be affected, but it is going to take some time. You might try writing a Good Will letter to the creditor on this and see if they go for it. If so, then the derog will be fixed.