I just found an answer on yahoo anwsers (Portuguese).
There are boats that take you from Manaus to Leticia. You just buy the ticket directly in the boat, there are no agencies. The schedule is a bit irregular but as a rule of thumb they go out every other day. The journey takes around 5 to 7 days. If two boats depart on the same day (apparently it can happen) you get 50% discount. You have to bring your own hammock to sleep.
Be careful. According to the text in the link Manaus can be dangerous due to drug traffic.
Meanwhile I found some more information on this forum. Apparently it's possible to negotiate with the boat owner and get a better deal for the ticket. The trip is actually to Tabatinga and not to Leticia. But these are sister cities. You can walk from one the other as you can see here.
You can get more information by calling the Manaus harbour:
PORTO DE MANAUS:
Phone: +55 (92) 3622-1330
Fax: +55 (92) 3233 2689.
According to this page these are the boats that make this connection:
- SAGRADO CORAÇÃO DE JESUS
- OLIVEIRA V
- DOM MANOEL
- MANOEL MONTEIRO II
- VOYAGER III
- M. MONTEIRO
- FÊNIX VOYAGER IV
And finally a website and another where you can search several routes from Manaus. They even show departure dates and contacts from the boat owner. Making reservations on-line is not possible.