Well, whatever the problem was, it was on the phone. After I factory reset Kies recognised the phone immediately, then upgraded firmware again to the latest version. Now the LAPTOP (which even Kies Air didn't work on) connects to Kies without a hitch.
I don't have a clue what would have been on my phone causing the issue, but my phone is now running better than the day I bought it, and Kies works.
So to anyone out there feeling the frustration I felt over the past year or so (especially the last 24 hours) here's what I would advise:
Copy your phone contacts to SD card
Backup SD cards
There are other options for backups online etc, but if you're stuck on an old version you might not get them working.
Obviously this isnt the only way, because I got Kies to recognise my phone before I upgraded and factory reset, I'm not sure if playing with Kies Air did the trick, or it was as simple as connecting to Kies mode on the phone, THEN running Kies on the computer.
If you're still stuck, remember I did a bunch of other things first, here's a short summary of them:
- Reinstall Kies
- Have Kies reinstall USB drivers
- Install Windows Mobile Device Centre
- Format SD cards (back em up first!)
- Go back to stock launcher
- Go through the Kies instructions for setting up Wireless Connections, this might sound pointless if you're trying to get the USB to work, but there were a couple of steps, such as editing a couple of services, and making sure mobile devices were allowed in Windows Firewall, which MAY have had a positive effect.
If anyone has the power you might want to mark this thread as fixed.