Pulled my hair out for a while when new-shortcut kept giving me the error "Specified path [“Path to my shortcut.lnk”] is not valid. The path was correct, and I tried every syntax alteration I could think of. Even just tried putting it to the root of C: to see if it would work. After successfully using my own shortcut script in PS with wscript.shell to create a shortcut with the same path, I knew something was wrong. After checking the new-shortcut function in AppDeployToolkitMain.ps1, on line 4984 where it is synchronizing the .NET current directory with PS working directory, there is the code: [IO.Directory]::SetCurrentDirectory((Get-Location)), which in my mind is just returning the literal path from PS and not the provider path that .NET needs, so I was able to find an example of synching .NET path with PS working directory and came up with this: [IO.Directory]::SetCurrentDirectory((Get-Location -PSProvider FileSystem).ProviderPath)
After making this change, new-shortcut worked as expected. So if anyone is having this issue in 3.8.4, making the change to that line will correct it.