I thought it would of been some security certifications that needed updating or my computer needed rebooting after an update.
After rebooting both client and host, the problem persisted.
Scouring the net for a while, I discovered that it was due to my recently updated nVIDIA drivers. Somehow, the new drivers were breaking Remote Desktop, and surprisingly this isnt just with nVIDIA drivers).
The drivers I downloaded were GeForce WinXP 32bit v175.19.exe, but the problem seems to have been from before that. I couldn't be bothered downgrading, so I looked for an alternative.
Luckily, there was an easy solution.
The problem: [ Source ]
The root of the problem is that the session image space is too small and it can't load any more drivers into it. The session image space is shared for the display driver drivers and printer drivers. rdpdd = remote desktop protocol display driver.
You can fix this bug by increasing the size of the session image space via a registry key.
The fix:
In the registry, go to "HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management" and add a new DWORD called "SessionImageSize"
Setting its value to 0x20 (hex) or 32 (decimal) will allocate 32mb to memory for the session image.
Reboot and your Remote Desktop should work again.