They had already implemented it, but were using a way of keeping the app running in the background that's reserved for apps that play music or track your GPS location. Apple rejected the app because Sparrow was neither.
Just wanting to point out there is a third option, though not indefinitely.