@Ben
Are you using Tiled maps? This is common if you're using a spritesheet that has no padding between each tile. If you modify your image to add a 1px padding between each tile and import it on tiled as such (telling it has a 1px pad) it should display fine.
In case you already made some tiles and don't want to manually rearrange it, I've used this gimp plugin in the past to automatically add padding (or do other modifications) to spritesheets:
http://registry.gimp.org/node/26044
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