I have an answer to a post from 2 years ago. Since it was an old post I am creating a new thread in case my answer will be of use to anyone, because it seems this problem is still occurring in Qt 4.8.
Description of the problem
A Mac application that uses 3rd party libraries is building and running OK, but when macdeployqt is run, macdeployqt complains it can't find the dylibs. I have had this error with Poco socket libraries and with my own suite of C++ libraries. I am not an expert on Qt, but here is what I did to solve the problem. If you look at the error message you may find it is saying that it can't locate the libraries in a directory called 'lib'. It may be that your 3rd party libraries were not built in a subdirectory called lib, they may have been targeted at a directory called 'release' or 'x86_64', or whatever. If this is so, create a peer subdirectory called 'lib' and make a copy of your build libraries there also. Now macdeployqt can find them. Disadvantage of this fix is having to keep the two directory contents in sync, so if anyone knows a better solution I'd be very pleased to hear it. It may seem the solution is to re-target the libraries, but that is not always convenient, especially if the libraries are used by multiple projects, some not involving Qt.