Music Composers Unite!
There could be a lot of potential problems here.
Firstly you need to ensure you have a pro audio interface (not a soundcard) and then use the ASIO drivers to connect to Cubase. Using software emulation or default drivers just won't cut it. If there aren't any ASIO drivers readily available then chances are you're using the wrong kind of audio interface. M-Audio definitely make some decent ones.
Once you have that running then you need to check what latency the buffer is set to. If you're still get pops and clicks at a setting of '512 samples' then there is a problem elsewhere.
If you're using very heavy VST instruments that stream from disk, have you set the streaming buffer too low? Are you using the same hard drive for running Cubase, streaming the VST instrument data AND recording your track? Ideally these should be three entirely separate physical disks.
Are you making sure that you're not overloading the output bus?
Did this project work in a previous DAW or on someone else's DAW?
My first thought would be the same as James.
Sample libraries should be streaming from separate physical drives than the one your apps are on.