Only "too" and "very" are currently accepted on the English side; both příliš and velmi (and some others) are accepted on the Czech side. I'm learning as well, but it seems to me that all of the accepted variants on the Czech side carry the feeling of "a lot," as opposed to something more specific like "excessively" or "overly." I will be happy to add those, however, if the CZ natives on the team feel they would be appropriate here.
Maybe I'm missing something that you're seeing, but the verb není simply means "is not." If we took away příliš teplý from the sentence just to simplify the grammar, we have "October is not a month." Clearly this isn't true, but it does seem to show that the "negation" not only belongs to, but is part of, the verb. (Just one person's opinion...)