Have you tried without padding between tiles? I've never used padding and never had problems. But always used tiled map parsing
make sure your texture is a power of 2 in size e.g 512x512 not 512x300. The non-power-of-2 will cause some drivers to scale the texture and make pixels appear to "bleed" as well.
