There is a bug in the portuguese hyphenation rules in babel. In portugese, when a word has an hyphen (like "cala-te") and must be broken at the hyphen, there should be an additional hyphen at the beginning of the following line. For example: XXX XX XXXXXX XX Olha, cala- -te, que XXXX XXXXX XX XXX Probably this won't be hard to fix, but I don't know enough of TeX/LaTeX to do it myself and post the fix instead of a bug report...
The version of tetex that you are using does not have hyphenation rules for Portugese. tetex-1.0.7-9 has all i18n hyphenation rules enabled.