Extract the files that you download into a new folder.
Use Shadow's Registry editor (
http://users.tt-forums.net/shadow/ ) to set the correct settings for TTD, using the folder you just created.
Copy the ttdpatchw.exe you downloaded into that folder.
Download the 'All new graphics' package from
http://www.ttdpatch.net/ and copy the files into your that folder too (should make a newgrf folder with lots of files in it).
Now create a ttdpatch.cfg with your settings in it (yours looked fine but mine is attached if you want it).
Now run ttdpatchw.exe and it should work.