"After a lot of research, I noticed that my paste issue only occurred when I had my browser running. It transpired, that is was when any browser (Firefox, Safari, IE, etc) was running.
Long story short, it was my Webroot security software blocking some of my programs which were attempting to read the Clipboard.
It makes sense, I have a browser open so I wouldn't want an untrusted application gaining access to my clipboard as it may contain a password. I just hadn't realized that it was doing this. When I disabled the Protect Clipboard Data option, everything worked again.
Webroot prompted me to disallow / allow a particular program to access the clipboard, with an option to remember my choice. So, I gave certain programs permission and then switched the protection option back on, as I think that it is a great feature.
I would guess that other security suites use this methodology so if you are experiencing paste issues, you may find it beneficial to check your security suites settings.