I am not sure if this solution is applicable to your case but, it solved everything for me, and I was experiencing the same thing as you did.
Ubuntu 13.10 & ATI Radeon HD 5450
A. Edit your GRUB file /etc/default/grub
old:
GRUB_CMDLINE_LINUX=""
fix:
GRUB_CMDLINE_LINUX="quiet splash nomodeset"
and save & exit.
$ sudo update-grub
$ sudo reboot
B. Update your flgrx installation
$ sudo apt-get install -y fglrx-updates
Configure your graphic configuration with AMD Catalyst
$ gksu amdcccle
This line will open the AMD Catalyst as Administrator (you will be prompted for superuser password to use it and this is the only way to get this to work)
Do your configuration as per your preference and save the setting.
Configure your X11/XOrg settings
Open your display setting [ Launcher --> System settings --> Displays ] and configure to your preference. This will reconfigure your system so it'd merge with the new configuration set by AMD Catalyst. AMD Catalyst is graphic adapter controller meanwhile System display configuration controls the X11/Xorg. With these steps above establishes the connection of configurations between adapter and X11, which will enable the updated flgrx to run.
"Ok, what was really the problem?"
The newer version of kernel have "standardized" the video mode setting but into inside of kernel. With that, it means kernel registers your graphic adapter first which in turn, prevented X11/Xorg being able to gain the control of this graphic. So, in order for your system to get the full control is to "inform" kernel to not register your graphic adapter, with this command: 'nomodeset'.
There were some reports that kernel version 3.7.10 and 3.8.3 doesn't do much but were solved by using 'modeset=0' (without single quotes when editing your grub).
Hope this helps.
Edit added:
As fallback solution - at the start up of your GRUB, enter 'e' to edit the file. Look for "quiet splash" line in the file you are about to edit and add "nomodeset" to "quiet splash" (important) so it'd look like "quiet splash nomodeset".
Sources:
How to set NOMODESET and other kernel boot options in grub2
My computer boots to a black screen, what options do I have to fix it?
nomodeset may no longer work >> use modeset=0 for graphical install on legacy hardware