Here is an interesting post about statistics, you almost definitely need to tune this on a database that large (based on the content of the post, not my experience.)
Thank you very much for your tips. PostgreSQL really have some issues that I didn't know about. I was thinking that the optimizer was not taking the best way for this query, but it's very difficult to find this out.
I'm out of access to the database right now, but as soon as I can I'll do this tuning and post the results back here.