Cette contruction vous choque du fait que l'adverbe ne modifie dans cette construction ni un adjectif qualificatif ni un autre adverbe. Il doit donc être placé devant l'un ou l'autre de ces mots. Il sera correct de le placer devant l'adjectif qualificatif "bonne" :
Il est parti de trop bonne heure.