yum install php
Loaded plugins: fastestmirror, priorities
Loading mirror speeds from cached hostfile
* base: centos.mirror.lstn.net
* extras: dist1.800hosting.com
* openvz-kernel-rhel5: mirror.fdcservers.net
* openvz-utils: mirror.fdcservers.net
* updates: centosv.centos.org
Setting up Install Process
Resolving Dependencies
--> Running transaction check
---> Package php.x86_64 0:5.1.6-32.el5 set to be updated
--> Processing Dependency: php-common = 5.1.6-32.el5 for package: php
--> Processing Dependency: php-cli = 5.1.6-32.el5 for package: php
--> Finished Dependency Resolution
php-5.1.6-32.el5.x86_64 from base has depsolving problems
--> Missing Dependency: php-common = 5.1.6-32.el5 is needed by package php-5.1.6-32.el5.x86_64 (base)
php-5.1.6-32.el5.x86_64 from base has depsolving problems
--> Missing Dependency: php-cli = 5.1.6-32.el5 is needed by package php-5.1.6-32.el5.x86_64 (base)
Error: Missing Dependency: php-cli = 5.1.6-32.el5 is needed by package php-5.1.6-32.el5.x86_64 (base)
Error: Missing Dependency: php-common = 5.1.6-32.el5 is needed by package php-5.1.6-32.el5.x86_64 (base)
You could try using --skip-broken to work around the problem
You could try running: package-cleanup --problems
package-cleanup --dupes
rpm -Va --nofiles --nodigest
The program package-cleanup is found in the yum-utils package.
[root@sever1 ~]# yum install php-common
Loaded plugins: fastestmirror, priorities
Loading mirror speeds from cached hostfile
* base: centos.mirror.lstn.net
* extras: dist1.800hosting.com
* openvz-kernel-rhel5: mirror.fdcservers.net
* openvz-utils: mirror.fdcservers.net
* updates: centosv.centos.org
Setting up Install Process
Package matching php-common-5.1.6-32.el5.x86_64 already installed. Checking for update.
Nothing to do

I've tried yum clean all and it doesn't seem to work :/

Thanks

First, as you are apparently using OpenVZ and not true CentOS beware of any advice from here.

Other Voices
When CentOS Is Not CentOS

You were trying to install php, possibly of a different version, when php is already installed. Did you try "yum update"?

If more help is needed then please provide more information about your system by running "./getinfo.sh" and showing us the output file.