<p>I'm building my app in vc2008 and testing it on a network of machines.</p>

<p>Is there any way, other than installing Visual Studio 2008, to run a debug build of a C++ program on another machine? (i.e. that doesn't have vc2008 installed)</p>

<p>Installing the redist package only installs the release mode support DLL's for vc2008 programs. Currently it complains that "This application has failed to start because the application configuration is incorrect. Reinstalling the application may fix this problem.", which I assume is code for "I'm missing DLL's".</p>

You can't, because there's no installer redist for the debug runtime (and in fact the software license forbids distributing it, so you'd be breaking the EULA even if you did get something put together). However, a "debug build" generally involves 4 separate options, and the other 3 don't affect distributing the app.
Generating a .pdb file (cl /Zi and link /DEBUG), which allows symbolic debugging. You probably want to add /OPT:ref to the linker options; the linker drops unreferenced functions when not making a .pdb file, but with /DEBUG mode it keeps them all (since the debug symbols reference them) unless you add this expicitly.
I generally do this with all my builds, even production ones. As long as you turn the linker optimizations back on with /OPT:ref it doesn't really cost anything, and having the symbols can be handy if you end up wanting to read a crash dump.
Using a debug version of the C runtime library (probably MSVCR*D.dll, but it depends on what runtime you're using). This boils down to /MT or /MTd (or something else if not using the dll runtime).
This is the one that means you can't redistribute things anymore. It also has a huge impact in the performance of some libraty functions, particularly memory allocation. The debug runtime versions are careful to "poison" the memory they touch with values to make uninitialized data bugs clear, the release ones generally leave the old data round to save the time touching it. I believe with the MSVCP* STL implementations the debug verions also omit all the allocation pooling that is usually done, so that a leak checker can show exactly the block you'd think and not some larger chunk of memory that it's been sub-allocating, but that means it makes more calls to malloc on top of them being much slower. If you have pointer or iterator handling bugs, this could affect what sort of misbehavior you get.
Turning off the compiler optimizations (/Od).
This one does lots of things (
this question
has some good discussion of the subject), but basically it hurts performance. A lot. Unfortunately, it's needed if you want single-stepping to work smoothly.
setting the preprocessor #defines DEBUG or NDEBUG.
This affects lots of libraries in various ways, but most notable it compiles in or eliminates assert() and friends.
So you might consider making a build with some lesser combination of these selections. I make a lot of use of builds that use have symbols (/Zi and link /DEBUG) and asserts (/DDEBUG), but are still optimized (/O1 or /O2 or whatever flags you use) but with stack frame pointers kept for clear backtraces (/Oy-) and using the normal runtime library (/MT). This performs close to my release build and is semi-debuggable (backtraces are fine, single-stepping is a bit wacky at the source level; assembly level works fine of course). You can have however many configurations you want; just clone your release one and turn on whatever parts of the debugging seem useful.
The only one that should impact trying to redistribute the app is 2.
If you're trying to debug on another machine, you might also be interested in
msvsmon
.