So, everything is installed ect. The HDD seems to be the tiniest of a fraction too small and it moves inside the laptop. Would something like cloth be okay to put in there or something similar to stop the HDD from moving?
Did you remember to remove the four pegs from along the long edges of your old hard drive with a screwdriver and attach them to your new hard drive? It won't fit snugly without those to hold it in place.
Also, you don't need to use Carbon Copy Cloner - you'll be at least as successul using Disk Utility on a Snow Leopard DVD (the one that came with your computer) to create a New Image (there's a button at the top of the screen for it) from your old hard drive's boot partition on an external HDD.
When you have the new hard drive installed, properly format your new hard drive in Disk Utility. Click on "Partition" while it's highlighted in Disk Utility (to the left of the Restore tab), change the Volume Scheme to 1 Partition, choose Mac OS Extended (Journaled) as the format (and name it whatever you like), and hit the "Options..." button below the partition picture to make sure you're using a GUID Partition Table (anything else and it won't be bootable).
Then when you have the new hard drive installed
and partitioned properly, use the Snow Leopard DVD Disk Utility again to Restore that image (there will be a few tabs including First Aid, Erase and Restore near the top but below that) to the partition you created on your new internal HDD.
Click "Image..." next to the "Source" text box and navigate to the .dmg you created; then drag the new partition (directly from the sidebar on the left) over to the "Destination" text box.
That's the whole process. You never have to use 3rd party software, and your HDD should fit snugly.
As an addendum, after you boot up your new hard drive for the first time, run Disk Utility and Repair Permissions on the new hard drive. The last time I replaced a HDD, it kept crashing until I did this - I'm guessing the image doesn't respect a lot of the file permissions from the original drive and may have messed up access to a kernel extension.
And one last thing: I wrote this assuming you're using Snow Leopard or haven't created a bootable install USB for Lion. If you're on Lion and created a bootable install USB, Disk Utility on that drive will also work.