Solution:

First, we provide some relevant graph-theoretic background. Any finite, connected graph can be turned into a tree (a connected graph without cycles) by removing some edges. Proof: If our graph has a cycle, any edge of that cycle can be removed without disconnecting the graph. So remove this edge, leaving a new graph. If it has a cycle, we can again remove an edge; continuing in this manner, we must eventually stop, since there are only finitely many edges to remove. We then have a graph with no cycles; since no edge removal ever disconnected the graph, it must still be connected.

Also, given a tree, we can choose a root vertex $r$. Then, for any vertex $v$, there is a unique path from $v$ to $r$, never repeating a vertex (uniqueness follows from the absence of cycles). We call $v$ a descendant of $w$ if this path goes through $w$. Every vertex is considered to be a descendant of itself and of $r$. Suppose $v$ is a descendant of $w$; then the path from $v$ to $r$ consists of the path from $v$ to $w$ followed by the path from $w$ to $r$. It follows that descent is transitive: if $w$ in turn is a descendant of $u$, then $v$ is a descendant of $u$. It also follows that $d(v, r)=d(v, w)+d(w, r)$, where $d(x, y)$ denotes the distance (i.e. number of edges in the path) from $x$ to $y$. Finally, a vertex $v$ with no descendants can be removed and the graph will remain connected. Proof: every other vertex is connected to $r$ by a path that does not pass through $v$, so these vertices will remain connected to $r$ - and hence to each other - when $v$ is removed.

Now we can solve our original problem. We state the graph-theoretic translation: given a connected graph $G$ on $k n$ vertices $(k \geq 0, n \geq 1)$, these vertices can be partitioned into $k$ sets of size $n$ such that $d(v, w) \leq 2 n-2$ whenever $v, w$ are in the same set. (In our case, $k=1999, n=2001$.) We prove this by induction on $k$. If $k=0$, we form no vertex sets, and the statement is vacuously true. Now suppose the statement holds for $k-1$, where $k \geq 1$, and we have a graph $G$ on $k n$ vertices. It suffices to prove the result when $G$ is a tree, since otherwise we can make it a tree by removing some edges and partition the vertices of this tree appropriately. The same partition will then work for the original graph $G$, since the distance between two vertices cannot increase when we put the deleted edges back.

So suppose $G$ is a tree, and arbitrarily choose a root $r$. Now let $a$ be a vertex for which $d(a, r)$ is maximal. Let $a=v_{1}, v_{2}, \ldots, v_{q}=r$ be the path from $a$ to $r$, and choose the smallest $i$ such that $v_{i}$ has at least $n$ descendants. (Some such $i$ surely exists, since $r$ has $k n$ descendants.) Let $S$ be the set of descendants of $v_{i}$; note that if $v \in S$, then every descendant of $v$ is in $S$, by transitivity. Notice that $v_{1}, v_{2}, \ldots, v_{i-1}$ are all descendants of $v_{i-1}$, so the minimality of $i$ implies $i-1<n$. Thus, $d\left(a, v_{i}\right)=i-1 \leq n-1$. Now we claim the distance between any two elements of $S$ is at most $2 n-2$. Indeed, suppose $b, c \in S$. We have $d\left(b, v_{i}\right)=d(b, r)-d\left(v_{i}, r\right) \leq d(a, r)-d\left(v_{i}, r\right)$ (by choice of $a$ ) $=d\left(a, v_{i}\right) \leq n-1$. Similarly, $d\left(c, v_{i}\right) \leq n-1$, and so $d(b, c) \leq d\left(b, v_{i}\right)+d\left(v_{i}, c\right) \leq 2(n-1)$, as claimed.

Now let $a_{1}$ be an element of $S$ at maximal distance from $r$. (For example, take $a_{1}=a$.) Then $a_{1}$ can have no descendants (except itself) in $G$, since if $b$ were a descendant of $a_{1}$, we would have $d(b, r)=d\left(a_{1}, b\right)+d\left(a_{1}, r\right)$, contradicting maximality. Thus, we can remove $a_{1}$ from $G$ to leave a graph $G_{1}$, which is still connected - in fact, still a tree with root $r$. Now a similar argument shows that, if $a_{2} \in S \cap G_{1}$ is chosen to have maximal distance from $r$, then $a_{2}$ can have no descendants in $G_{1}$ : any descendant would lie in $S$, by transitivity, and it would also be farther from $r$ than $a_{2}$, violating maximality. So, deleting $a_{2}$ from $G_{1}$ gives another rooted tree, $G_{2}$. Then, we can choose $a_{3} \in S \cap G_{2}$ to be maximally distant from $r$, and so forth. We continue removing vertices in this manner; since $S$ has at least $n$ elements, we can remove $n$ vertices. Thus, we choose distinct vertices $a_{1}, a_{2}, \ldots, a_{n}$, all of which lie in $S$; this means that any two of these vertices are at distance $\leq 2 n-2$ from each other, and the remaining graph, $G-\left\{a_{1}, \ldots, a_{n}\right\}$, is still a tree. Now using the induction hypothesis, this remaining graph can be partitioned to form the remaining $k-1$ sets of vertices, and the desired partition of $G$ is accomplished.