I've seen some people reporting problems with Makefile spitting the "psp-config error not found" error in their face. I encountered this problem tonight after a fresh reinstall of my pc. I found the cause.
A quick note: I'm using the win32 sdk available at http://www.xorloser.com. I'm not sure if the following solution is correct for Cygwin users, but the win32 sdk sorta indirectly uses Cygwin anyway, so at least give it a shot :)
I had my paths set up correctly, so I preceded to get my makefile to dump the PATH variable. As it turns out, lo and behold, look what's first on the list: "C:\Program Files\Microsoft DirectX SDK (April 2006)\Utilities\Bin\x86" ... including the quotes.. I had a hunch that if the spaces weren't confusing Cygwin, the quotes sure as hell would be.
After this, I tried placing C:\pspdev\bin (or C:/cygwin/usr/local/pspdev/bin for you Cygwin users) at the beginning of the list, and everything worked fine.
Bizarre yes. I think it has something to do with the way cygpath is converting the paths to /cygdrive for make... Or something. The reason I knew my DirectX path was messing up cygwin was because when I got my Makefile to echo the path variable, everything was converted over to the /cygwin/c path format EXCEPT for the DirectX SDK.
So basically, if you're having problems with Makefile not finding psp-config or psp-g++ and you're positive you set the paths up, try moving the PSP related paths to the beginning of the path list.