check out synaptic.
php5-cli requires php5-common
sudo apt-get install php5-cli works just fine in ubuntu 9.see if u can find it in synaptic.
Zero idea why you are having this problem if it worked fine on the same distro tho. Note that I am by no means qualified to give you any advice what so ever.