Are you installing Php using the dpkg command, or the apt-get or aptitude command?
If you are using dpkg, try this instead:
sudo apt-get update <-- this will refresh your repository caches
sudo apt-get upgrade <-- this will upgrade your system
sudo apt-get install php <-- this will install php
You may have to put php5 instead of php after apt-get install.
Welcome to LinuxQuestions.org and please, make sure you give plenty of details and stay in touch!