In order for /usr/lib/TclImage0.45/pkgIndex.tcl to load a symbolic link should be created in a directory like /usr/lib/tcl8.5/. For Fedora 13 I did a link with...
ln -s /usr/lib/TclMagick0.45/ /usr/lib/tcl8.5/
The build was accomplished with...
./configure --with-tcl=/usr/lib/ --with-tk=/usr/lib/ --with-magick=/usr/bin/MagickWand-config
...because Fedora puts 'tclConfig.sh' and 'tkConfig.sh' in /usr/lib/. It would be difficult to construct a symbolic link from the above command as the actual tcl directory is not listed. Fedora does put a symbolic link in /usr/lib/tcl8.5/ to the config file in the parent directory but no link exists in /usr/lib/tk8.5/ so you could not specify the tcl and tk directories consistently. This has the side effect of causing TCL_PREFIX and TCL_EXEC_PREFIX to default to /usr/ which is incorrect but doesn't seem to cause a problem.
1) Add the above to the README so people will have a shot at fixing this on their own.
2) Fix configure script to test for tclsh, run it with a tcl program to output tcl_version, and then locate the place for the symbolic link.
I would be willing to help with item 2 if you wish. Let me know. I can test on Fedora and Ubuntu.