Try this: Window->Open perspective->Other... The CDT perspective should be there unless an error occurred while installing.
EDIT: Also make sure that Eclipse C/C++ Development Tools are listed in your installation details. Help->About Eclipse SDK->Installation details
So the solution was to manually install Eclipse so that apt didn't install dependencies that were not actually dependencies.
Installing Eclipse Manually
So download Eclipse from here. I decided to use the Classic version, but if you want to use the Java EE version I'm sure that it will work.
Download it to a directory and open your terminal. Navigate to that directory by using the command
cd <insert directory path here>
Make sure that there are no files starting with eclipse in that folder. If there are then move them out of the folder temporarily. Then do this command:
tar -xzvf eclipse-*
Next,
sudo mv eclipse /opt/eclipse
Then you'll need to create a .desktop file for Eclipse in /usr/share/applications/eclipse.desktop so you have a shiny icon on your bar thingy (if anyone knows the offical name of the little bar on the side then please edit this answer so that it contains it). Do these commands
sudo touch /usr/share/applications/eclipse.desktop
sudo gedit /usr/share/applications/eclipse.desktop
Paste this in that file:
[Desktop Entry]
Version=4.2
Name=Eclipse
Comment=Integrated Development Environment
Exec=/opt/eclipse/eclipse
Type=Application
Icon=/opt/eclipse/icon.xpm
Terminal=false
NoDisplay=false
Categories=Development;IDE
Then create a symlink in /usr/local/bin so you can run it from the terminal using the command eclipse:
cd /usr/local/bin
ln -s /opt/eclipse/eclipse
That's it!
Eventually, I decided to use Sun's Java because OpenJDK was a substitute, and if I was going to do it manual, I might as well go the extra mile.
Best Answer
I used apt-get purge eclipse and then apt-get install eclipse and it still did the same thing. I ended up purging Sun JDK and reinstalling Eclipse and it installed OpenJDK. All works again.
However, I'm a little disappointed that it wasn't working with Sun JDK. Oh well. Whatever.