Well I had a similar problem. I have used 3 linux distros till now, and in all 3 the problem has happened when my "hostname" wasn't configured properly.
When I used to run "gnome-system-monitor", I found that the processor activity remains zero for a very long time after I execute a program. Then it jumped to 100% and the program would load. Is something similar happening in your case?
And the problem didnt happen in runlevel 3, it happened only when I started the X server.
So check it out, try setting your "hostname" properly in the internet connection settings.
I hope it helps