Then to my disappointment, I found that the laptop started to misbehave after sleep. Usually when I wake it up it, it takes just a couple of seconds to enter my password and everything is ready for work. However, this time instead of the password prompt, I got the infamous spinning beach ball ... and about 40 seconds later, the system finally asked me for my password. And this happened every time I woke the laptop. It's a minor thing, but quite annoying!
To make a long story short, after much investigation and futile digging through log files and debug modes of different system daemons, I found the culprit and hope I can help save some time for others. The problem was that the new hard drive came with its jumper set to "Cable Select" (CS) mode, and I decided to leave it as is. It looks like OS X doesn't handle this case properly, and instead of the expected one to two seconds, it took about 40 just to initialize the drive. As soon as I set the drive to master mode, everything returned to normal and now it works exactly as before. So if you have issues like delayed boot start or wake ups, check your hard drive's mode and try to avoid CS -- it worked for me, at least...

