Right, I think I've sorted the Kies3 issue:
Open your Kies3 app.
Connect the phone to PC via USB and attempt a connection through Kies3.
If (when) this doesn't work, close the 'failed to connect' message.
Leave your phone connected to the PC and (on Kies3) go to Tools>>Reinstall Device Driver.
After around five minutes, the phone will connect and your PC will announce that it now found your phone.
Hope this helps people out!