It had padding, but the padding was white. Apparently each tile needs to have padding of the same color as the pixel next to it. That seems a completely backwards way to deal with this -- isn't this simply a bug in libGDX that shouldn't occur?
Anyway, I wasn't using a TiledMap but I am planning to implement that soon