Hi Roger,
the problem is related to the default behavior of GDAL warping core,
which sometimes does not have enough input pixels or has a problem to
calculate correct target extent.
What you can do is to warp your input data into EPSG:900913 by
gdalwarp utility before tiling by gdal2tiles utility
I've gotten the map tile output from gdal2tiles.py to work properly with
Tilecache and the results look pretty good. However, I'm seeing a fairly
large gap in data at the international dateline. I recall seeing some
discussion about this between Frank and Klokan on the list previously, and
recomp