Also, in PhotoShop (and probably every other bitmap editor) there is a filter/function called Offset.
Set the Offset to 256 horizontal by 256 vertical, with "Edge wrap" on. The sides of the tile are now in the middle of the file. Clean up the seams, and re-Offset the file back to normal.