Sounds like you are going through what I went through. Same year, same creditor (Providian) and similar amount.
Here's what I did for what it's worth.
I sent a debt validation letter to them in November 2007. They responded in about 30 days claiming I owed the debt. They were piling on about $4,500 in interest charges to a $6,900 debt that they purchased from Providian for pennies on the dollar. I challenged them with a letter (sent certified with return receipt requested) demanding that they provide me with the interest amount and how it is being calculated. They are obligate by law to provide you with that information. They never did respond.
Fast forward to March 2008. I sent a goodwill letter to them explaining that I would be willing to make 4 installment payments for payment in full (I would not pay them any interest) and they would have to agree to permanently delete the trade line (in writing) from all three credit reports. I also wrote in the letter that I will not negotiate those terms and will be sending a cashier's check with a restrictive endorsement on the back of the check that made it clear what the terms and conditons are for cashing the check. They never responded.
So, in good faith, I made three payments out of the 4 installments and stamped on the back of the check 'Portfolio Recovery Associates agrees to update all three credit reports as 'Paying As Agreed' upon cashing or depositing this cashier's check'; the final installment shall be payment in full and PRA agrees to permanently delete this trade line from all three credit reports'.
I sent a letter every 2 weeks until July 2008 reminding them of their obligation to update my credit reports which they failed to do. I also engaged their local branch of the Better Business Bureau with an ethics complaint against them and this helped tremendously.
Bottom line?
Portfolio Recovery deleted the trade line from all three reports on July 31, 2008. They actually sent me a letter of apology and a copy of the Universal Data Form that they sent to all three credit bureaus with the box checked 'Permanently Delete'.
Keep at them and don't get discouraged. Challenge everything and be prepared to spend a lot of time and energy writing letters. Keep hammering away at them and eventually you'll get results.
It took me 8 months but I won and it was on my terms.