The 'paintshed' utility was removed from TC/TS2009, since it is now an extremely out of date program.
That said, there are other ways of reskinning a locomotive.
You use an image editor (paint, paint.net, the gimp, paint shop pro, photoshop, and others) to repaint the textures. Not all locomotives can be repainted in this way (some have very simple textures that don't lend themselves to reskinning), same as only a very small number were able to be reskinned in paintshed.
A very basic guide to reskinning:
*Open CM2
*Locate the asset you want to reskin
*'Clone' the asset
*Open the asset in CCP, and edit the name, author, etc.
*Open the asset in explorer, and open each texture file (.tga and .bmp files, with the odd .jpg and .texture file sometimes) and repaint them.
*Commit the asset, and look at it in Trainz.
Others should be able to offer a more comprehensive explanation.

Zec