Found a fix for this.
I needed to hook up composite video from my TiVo to my Slingbox, then from the Slingbox to my TV.
The problem occurs when the TiVo had two output signals, one to the TV via HDMI and one to the Slingbox via composite video. When I turned off the TV, for some reason, the TiVo's playback was all messed up through the composite video. Whenever I turned off the TV, the stuttering occurs, but when I turn on the TV, the stuttering over the Slingbox is gone.
I have no clue why this is so.