We present kinematics of 135 planetary nebulae (PNs) in M31 from a survey covering 3.9 deg super(2) and extending out to 15 kpc from the southwest major axis and more than 20 kpc along the minor axis. The majority of our sample, even well outside the disk, shows significant rotational support (mean line-of-sight velocity 116 km s super(-1)). We argue that these PNs belong to the outer part of M31's large R super(1/4) bulge. Only five PNs have velocities clearly inconsistent with this fast rotating bulge. All five may belong to tidal streams in M31's outer halo. One is projected on the Northern Spur and is counterrotating with respect to the disk there. Two are projected near the major axis at X = -10 kpc and have M32-like velocities; they could be debris from that galaxy. The remaining two halo PNs are located near the center of the galaxy, and their velocities follow the gradient found by Ibata and coworkers, implying that these PNs could belong to the Southern Stream. If M31 has a nonrotating, pressure-supported halo, we have yet to find it, and it must be a very minor component of the galaxy.