First of all, I really love and appreciate you guys sharing your methods on this topic. In particular, I'm a big fan of both of your ROM work and your graphics.
Here's my quick notes on my graphic editing approaches:
I export any graphics from TM (v0.16) to png
I use MS Paint instead of Photoshop. I don't know if there are advantages to Photoshop for bitmap editing, but Paint seems to work well.
Similarly to you all, I manually rearrange tiles to the full picture in Paint, and keep a reference map of the original picture.
I make any changes in Paint. If I use new/custom colors, I then use @smozoma's Ditherer program to convert it to '94 colors. I have tried other various methods, but that program saves me a lot of time and I am generally happy with the results. Especially with the knowledge/expectations of my color limits to begin with.
Once satisfied, I re-cut the tiles back into the original layout and paste back in using TM.
FYI, I think TileLayer Pro is a TM alternative that has this arrangement functionality built in, but I was never good with using that program. At the same time I rarely need to do this kind of editing as much of the graphics work I do has been rearranged already (or I rearrange in the ROM layout).