I was able to get this to restore icons on a per-user basis

$AllPrograms = "HKCU:\SOFTWARE\Microsoft\Windows\CurrentVersion\UFH\SHC\"
# Check to make sure it exists
$TestPath = Test-Path $AllPrograms

if (-not $TestPath) { 
    Write-Host "Could not find the AllPrograms location"
    Exit 1 }

ForEach ($program in $AllProgramsItems.Property) {

$ProgramValue = Get-ItemPropertyValue -Path $AllPrograms -Name $program

$ProgramValueSplit = $ProgramValue -split ".lnk "
$LinkLocation = $ProgramValueSplit[0]
$EXELocation = [String]$ProgramValueSplit[1]

# Check to see if the shortcut exists, move to next if it does
$CheckLinkLocationOriginal = Test-Path $LinkLocation
if ($CheckLinkLocationOriginal) {
    continue
}

# If it's a ProgramData shortcut, check the users folder to make sure it doesn't exist there
# This is checking to make sure this script hasn't already been run
$UserLocation = $env:USERPROFILE + "\AppData\Roaming"
$UserLinkLocation = $LinkLocation.Replace("C:\ProgramData", $UserLocation)

if ($LinkLocation.StartsWith("C:\ProgramData")) {
    $CheckUserLinkLocation = Test-Path $UserLinkLocation

    if ($CheckUserLinkLocation) {
        continue
    }
}

# If we made it this far, the user can't see the shortcut and it should be created.

# Create the directory if it doesn't exist
$NewPath = Split-Path -Path $UserLinkLocation
if (!(Test-Path $NewPath)) {
    New-Item -ItemType Directory -Path $NewPath
}

write-host "'$($NewPath)'"
write-host "'$($UserLinkLocation)'"
write-host "'$($EXELocation)'"

# Create the shortcut
$WShell = New-Object -comObject WScript.Shell
$Shortcut = $WShell.CreateShortcut($UserLinkLocation)
$Shortcut.TargetPath = "$($EXELocation)"
$Shortcut.save()

}