I have tried several different solutions of getting this sound to stop when playing back somewhat larger scores. Take for example a concert band with basic keyboards and accessory percussion. When I hit play, the sound will sometimes skip or repeat the initial note for a while then move one. Another problem is when this happens a constant gurgling sound comes out. Basically my ";players are under water";... :/
This randomly started happening shortly after the Sibelius 7 upgrade.

Specs:
Sibelius 7.1
VDL 2.5.2 in Kontakt 5 (plug-in)
ASIO4ALL v2
Windows 7 64-bit
Intel Core2 Duo 1.3GHz
4.0GB RAM

You might be reaching the limit of your system- a 1.3 GHz cpu is definitely on the low-end of things.  Try increasing the buffer size- this will allow more voices to be played, but there will be some delay when you hit your MIDI keyboard to enter notes.  You might want to switch to the ";lite"; versions of the instruments.

With Sibelius 6 everything played back perfectly fine, but now with 7 it has been terrible. I will definitely try increasing the buffer size.

I am using the latest version of the ASIO4ALL Audio Interface and I have had the buffer size set to the max of 2048 Samples with Latency being 68.62. Everything plays back just fine but then it starts the skipping and the gurgling again, so I just ";restart"; ASIO by re-selecting it in the audio interface, and then everything plays back just fine. Any ideas? Could it just be my CPU? I don't see how seeing as Sibelius 6 I never had this problem.

What kind of sound card are you using? You may want to look into this and what sort of driver you're using in conjunction with it. Ideally, ASIO4ALL is a last resort when using a cheaper soundcard without ASIO support. If, however, your soundcard supports ASIO natively, you'll likely see better audio performance.

Realtek High Definition Audio.

I did notice today that my ";Graphics Mode"; which switches to the NVIDIA Graphics Card instead of the Intel was switched off and I did seem to have significant improvement with sound and speed.

Your mileage may definitely vary with a soundcard like that. You may also want to check that your drivers are up-do-date. Here's a site with some more info.
http://www.driverupdate.net/new_lp/realtek_lp.php#common_problems

Eventually, you may want to consider upgrading to an audio interface that's a little more geared towards audio performance. Something you'd shop for with a music dealer rather than an electronics/computer store like Best Buy, etc.