Solution:

From $z + \frac{1}{z} = 2\cos 3^\circ$ we get $z^2 - (2\cos 3^\circ) z + 1 = 0,$ so $z = \cos 3^\circ \pm i \sin 3^\circ,$ a point on the unit circle. By de Moivre's theorem, $$z^{2000} + \frac{1}{z^{2000}} = 2\cos(2000 \cdot 3^\circ) = 2\cos 6000^\circ.$$

Since $6000 = 16 \cdot 360 + 240,$ this equals $2\cos 240^\circ = -1.$ The least integer greater than $-1$ is $0.$