...Like I said, some programs (dundjinni, mapx, dungeonforge) support random tiles automatically, but Gimp doesn't...

The base seamless tiles would look like this:
Click image for larger version. 

Name:	seamless_1.jpg 
Views:	298 
Size:	362.6 KB 
ID:	7273

Setting the grid to 200px, and turning on snap to grid, I create a new layer and drag in copies of the other tiles, snapping them to the grid:
Click image for larger version. 

Name:	2008-10-22_130309.jpg 
Views:	162 
Size:	452.3 KB 
ID:	7274

So when you look at the whole thing you get less periodicity:
Click image for larger version. 

Name:	seamless_2.jpg 
Views:	207 
Size:	362.5 KB 
ID:	7275

One last thing that can be done is to add a B&W overlay. Here I added a gradient to shade the image a bit. This fools the brain and makes the texture look less periodic:
Click image for larger version. 

Name:	seamless_with overlay.jpg 
Views:	165 
Size:	362.3 KB 
ID:	7276

One last note. I showed the cutting out a feathered frame, and using the same frame for all of the tiles. A better method (that I figured out after doing this) would be to use layer masks to randomly mask the outer edges from each of the dragged in copies to expose the seamless tile below. This would give more control to eliminate small inconsistencies or details that would show up periodically, in a non-destructive manner.

-Rob A>