Been there, done that, burned the t-shirt.
My personal favorite was getting a call from a client on my cell phone while I was driving on the interstate. I didn't have a computer, I didn't have code, and I wouldn't have been able to use either one if I did. Fortunately, it was code that I'd just written, so I was able to step through it by memory.
My second-favorite phone-coding experience involved writing a WAV/AIFF codec in Fortran, which I haven't spoken in many, many years. The client was trying to port a program that relied heavily on pipes to subprocesses from Linux to Windows NT. The codec was one of the things that broke, and since the bulk of the code was in Fortran (heavy numerical processing), the client wanted me to replace the subprocess with built-in code.
The best advice I have for such situations is: use lots of small steps.
The biggest problem of working with code is getting lost.. even when you have the code right there in front of you. If you try to do too many things at once, you'll eventually suffer a mental stack overflow and segfault your brain. And when you're debugging by proxy, you also face the risk of segfaulting the other person's brain. Keep the tasks small, and make sure to clean up after yourself every step of the way.
Beyond that, debugging over the phone follows most of the same rules as regular debugging. The first (and usually biggest) problem is diagnosis. Start at the point where things obviously go wrong, and start inserting print statements. Dump out the variables to see what the values are, and locate the ones that don't look like they should. Trace those back until you find the statement or function where good input values produce bad output values, they try to figure out what's going wrong.
If you're lucky, the problem will be obvious once you know the exact location of the misbehaving code and have a sample of input that makes it misbehave. If you're not lucky, the problem will involve subtle interactions with other parts of the code, or possibly the OS. If it's a well-behaved bug, you should be able to chant off a code patch right there on the phone, and the client will go away feeling vaguly privileged to have worked with such a guru.
OTOH, it's not worth the pain of trying to debug a subtle bug over the phone. Identifying it as a subtle bug is enough for an ad-hoc debugging session, but the solution will probably involve deep design changes, and should be handled accordingly. If you discover that you're dealing with a subtle bug over the phone, just say, "Okay, this one is too tough to resolve here and now. You talk to your superiors and I'll talk to mine, and we'll work out a deal where we can solve this thing properly."