Did you run <tt>texhash</tt> (same as <tt>mktexlsr</tt>)?
If not, do it – it rebuilds TeX's lsR database, used by <tt>kpathsea</tt> to find your files. Often the command needs administrator rights to take effect, on UNIXy OSes (Linux, MacOS X) try <tt>sudo texhash</tt>, on Windows XP you might need <tt>runas</tt>.
(In MikTeX there's a similar command, "rebuild database" or the like.)