Until we have a few more specifics on your platform/OS/compiler, it's going to be hard to answer, but in the mean time, look at this answer to "In general how often and when should I optimize my code?" for some generic suggestions.
Most of these suggestions will work equally well in optimized (release) or non-optimized (debug) builds.
(I'll return and update this answer with more specific tools and ideas if you update the question with more details.)
Edit: okay, more specific suggestions.
Take a two-pronged approach. One, do exactly what Simon is suggesting -- build a lightweight "stopwatch" timer into your code. It doesn't have to be pretty to start with -- as my link above suggests, you can always "drill down" from coarse info to finer-grained info.
Second, take advantage of the free (gratis) tools. Even if you don't get exactly the info you want, scope out a sampling profiler such as AMD CodeAnalyst. This shouldn't have problems with threads, and should be capable of giving you a "code was often in this place" readouts, or even full stack traces. While it may be a little harder to reason about the masses of data you'll get here, chances are you'll see something, and it has the advantage of being non-intrusive. If you have an AMD processor CodeAnalyst will even do the performance counter stuff for you, giving you access to e.g. cache miss and branch prediction info.
It might be fun to take valgrind's cachegrind, callgrind, or massif across the project. This is definitely going to slow things down but you may learn a lot. The valgrind memcheck module is worth knowing about too.
You may also want to investigate the GCC's intrusive gprof. Sampling profilers are generally observed to be a better idea (they don't alter what they're looking at quite as much), but you may also learn something from gprof's complete instrumentation that you couldn't see using sampling.
None of this gives you great visibility into the lua parts. You'll get stack samples or call info from within lua, and you might be able to infer what it's doing with per-line or per-instruction samples. But it may not be easily decomposable into "which scripts took the most time" or "which line of this script is giving us the most trouble". For that you'll need to either look into a commercial lua engine, or just extend your stopwatch tool a bit...
(There was a game middleware company offering a fully custom lua engine with profiling and debugging tools, can't find them now... There's also lua profiler, googling around a bit. Not sure if it would fit the bill, but it seems like there are others too.)
If you're willing to take the time to play with CodeAnalyst, valgrind, or gprof, chances are you'll learn something -- if not about your code, then about profiling in general, which you might use to enhance your own custom solution. =)