Did you try updating the statisitics with a FULL SCAN? They're pretty widely out of line. That's frequently an indication that they're out of date.
You're getting a loop join on 10000 records. That should be a hash, I'm sure.
I'd try updating the statistics again, using the full scan. The optimizer is making some pretty poor choices here.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning