<p>I'm stuck on a PHP 4 server, and I would like to start moving an old legacy project to modern Design Patterns, including Dependency Injection.  Are there any dependency injection frameworks that will work with PHP 4?</p>

I don't think a dependency injection framework will really work on PHP because of the way object-oriented programs are structured in it. First of all, it's not like C# or Java wherein the binaries are already there and you just have to find a way to instantiate this object and inject it into another. PHP has to load the class files and interpret them before it can use them. So if you have deep inheritance hierarchies with PHP I don't think that's a good idea.
Given that PHP is a scripting language, it's best to leverage it as that -- a scripting language. Which means, I would just make use of simple factory or builder methods to do something similar to dependency injection. I wouldn't burden it with a DI framework that will only add to the stuff the PHP runtime has to process for every web request (unless you do opcode caching, but there will still be overhead that's not incurred by web platforms for Java and .NET). If I have to change the objects that will be injected into objects or how they are created, it would be a simple task to just edit the script that contains the factory/builder methods. No need to recompile there anyway. So I have flexibility and I have a lightweight architecture that's suitable for the PHP way of doing things.