The Pan Andromeda Archeological Survey (PAndAS) CFHT Megaprime survey of the M31-M33 system has found a star stream which extends about 120 kpc NW from the center of M31. The great length of the stream, and the likelihood that it does not significantly intersect the disk of M31, means that it is unusually well suited for a measurement of stream gaps and clumps along its length as a test for the predicted thousands of dark matter sub-halos. The main result of this paper is that the density of the stream varies between zero and about three times the mean along its length on scales of 2-20 kpc. The probability that the variations are random fluctuations in the star density is less than 10(-5). As a control sample, we search for density variations at precisely the same location in stars with metallicity higher than the stream [Fe/H] = [0, -0.5] and find no variations above the expected shot noise. The lumpiness of the stream is not compatible with a low mass star stream in a smooth galactic potential, nor is it readily compatible with the disturbance caused by the visible M31 satellite galaxies. The stream's density variations appear to be consistent with the effects of a large population of steep mass function darkmatter sub-halos, such as found in LCDM simulations, acting on an approximately 10 Gyr old star stream. The effects of a single set of halo substructure realizations are shown for illustration, reserving a statistical comparison for another study.