In a language such as (since I'm working in it now) PHP, which supports procedural and object-oriented paradigms, is there a good rule of thumb for determining which paradigm best suits a new project? If not, how can you make the decision?
It all depends on the problem you're trying to solve. Obviously you can solve any problem in either style (procedural or OO), but you usually can figure out in the planning stages before you start writing code which style suits you better.
Some people like to write up use cases and if they see a lot of the same nouns showing up over and over again (e.g., a person withdraws money from the bank), then they go the OO route and use the nouns as their objects. Conversely, if you don't see a lot of nouns and there's really more verbs going on, then procedural or functional may be the way to go.
Steve Yegge has a great but long post as usual that touches on this from a different perspective that you may find helpful as well.
If you're doing something for yourself, or if you're doing just a prototype, or testing an idea... use the free style that script languages gives you.
After that: always think in objects, try to organize your work around the OO paradigm even if you're writing procedural stuff. Then, refactorize, refactorize, refactorize.