It's throwing the error because it's failing to sort them by Date/Time due to a hotfix with a InstalledOn entry that can't be parsed into a valid Date/Time.
So, most likely you have HotFixes installed on the one machine that don't have a proper "Installed On Date", and so it just returns blank for those entries.
This is not specific to a version of Windows, as I tested this on a Windows 2012 R2 server, and saw the same error.
You can confirm the InstalledOn dates by running the query without the sort:
Get-Hotfix -cn HOSTNAME | select HotfixID, Description, InstalledOn -first 20
PS C:\Windows\system32> Get-Hotfix | select HotfixID, Description, InstalledOn -first 20
HotfixID Description InstalledOn
-------- ----------- -----------
KB2868626 Security Update
KB2894852 Security Update 01Dec2015 12:00:00 AM
KB2900986 Security Update
KB2919355 Update 04Oct2014 12:00:00 AM
Note above that many of them show nothing for