The wrong hyphenation patterns in the text were caused by the wrong
hyphenation module being used. Since latex can't find a hyphenation
module for Brazilian Portuguese, it loads the default, English. A
message is shown on latex's output:

    Package babel Warning: No hyphenation patterns were loaded for
    (babel)                the language `Portuguese'
    (babel)                I will use the patterns loaded for
    \language=0 instead.

Unfortunately, support for other modules requires latex recompilation
(didn't test that, firmly believing the source here). The solution for
now is to use a hyphenation file, correcting the wrong patterns. Mental
note added for future projects.

Source: http://stackoverflow.com/a/3823221/2081353