« Avant qu’il ne parte » a le même sens que « avant qu’il parte ». On se passe dans l’usage courant de ce « ne » dit explétif, qui n’est pas à proprement parler négatif (Bon usage, § 1023). On explique son emploi dans des contextes ayant une coloration négative. Le plus important est le complément d’un verbe de crainte : « je crains qu’il ne fasse fausse route » (Bon usage) car, au fond, quand on craint quelque chose, on souhaite que cela n’arrive pas.
« Avant que » situe la subordonnée dans un moment postérieur à la principale : « Elle parvint à rentrer dans la cuisine quelques moments avant qu’Orso ne parût » (Mérimée, « Colomba »). Comme l’action est à venir, virtuelle et pas encore réalisée, elle est présentée avec une certaine incertitude, qui la colore de négativité.
Il est d’ailleurs difficile de formuler une négation véritable avec « avant que », ce qui est possible après un verbe comme « craindre » : « Je crains qu’il ne vienne pas / plus/ jamais... ». Comme quoi l’avenir n’est jamais sûr.