I had the same problem. I even upgraded my hard drive, as it was failing and I thought it caused the problem. However, after upgrading the drive, the problem persisted. It was driving me nuts to waite for all the app to start working again and for internet to be up. I tried many solutions posted online, nothing worked. I reinstalled Lion and nothing.
What did help me, was turning off the computer. Then turn in back on and at the same time press and hold "D" (try to press "D" before grey screen appears). Hold "D" untill the computer starts, It could take up to a minute. While holding, I notice "folder" icon on my grey screen with question mark inside. I kept holding "D" until my comp started up. I didn't bother to check if that fixed the problem. However, after I closed the lid on my macbook and opened it later on in a few hours I saw a miracle :-) It literally took 2 seconds for every app and internet to be up and running. I couldn't believe it, but it helped. Try it, it might help you too.