What sometimes happened to me was, that when loading a foreign template for Cubase, the sound driver was set to some generic type, which I didn´t notice at once..
When latency began to be a problem, you check the buffer sizes of your audio card and everything looks fine, although you can notice a big lag.
Check if you definately selected and activated the right ASIO driver.
Other things to check : Do you use an effect chain, perhaps convolution reverb or an external effect processor ( TC, UAD, SSL ) ?
What happens if you click on the virtual keyboard with the mouse instead of using a Midi keyboard ?
Can you go down to 128 samples without drop outs ?
256 should also be O.K., but maybe a little bit on the edge if you are critical.