Loss of admin privileges when Java program calls C# program to write to %ProgramData%

The scenario:

1. I have a Java based installer.
2. The Java based installer calls a C# program, whose job is to create a shortcut.
3. The shortcut location depends on if the installer is running as administrator or as a regular user. When running as admin, I'm trying to create a shortcut to "%ALLUSERSPROFILE%\Desktop", else I write to "%USERPROFILE%\Desktop".

My impression is that the issue seems to be a loss of administrative privilege when my Java program calls my C# shortcut maker program.

Notes:

1. I run my Java based installer as administrator (right click, run as administrator).
2. I'm able to verify the installer is running with administrator privileged because I can read registry keys that require administrative privilege.
3. I'm calling my C# program via 'Process process = Runtime.getRuntime().exec(command);'
4. When running the command manually through an administrative command prompt, the command works fine. (When outputting to "%ALLUSERSPROFILE%\Desktop")
5. When running the the same command manually, from a normal command prompt, I get System.UnauthorizedAccessException. (Which is to be expected). The program crashes in a similar was that it does when run from the installer.

The Exception:

Unhandled Exception: System.UnauthorizedAccessException: Access is denied. (Exception from HRESULT: 0x80070005 (E_ACCESSDENIED)) at IWshRuntimeLibrary.IWshShortcut.Save()

Any thoughts on what I'm missing? The installer needs to be flexible to run as both a normal user and as an administrator. How can I ensure this behavior?

Update 1

I attached a debugger to the C# program at runtime. It is throwing a:

DirectoryNoFoundException was unhandled 
The system cannot find the path specified. (Exception from HRESULT: 0x80070003)

I added "mkdir" commands before my shortcutmaker commands. The mkdir commands, just ensure that the directories exist before trying to write to them.

Rebuilt the installer, ran it and when trying to mkdir "%ALLUSERSPROFILE%\Desktop", java throws an exception of

java.io.IOException: Cannot run program "mkdir": CreateProcess error=2, The system cannot find the file specified
java.io.IOException: Cannot run program "mkdir": CreateProcess error=2, The system cannot find the file specified
        at java.lang.ProcessBuilder.start(Unknown Source)
        at java.lang.Runtime.exec(Unknown Source)
        at java.lang.Runtime.exec(Unknown Source)
        at java.lang.Runtime.exec(Unknown Source)

At this point, it looks like my process isn't getting admin access

        Process process = Runtime.getRuntime().exec(command);

I'm going to see if I can find anything else.

Update 2

The following gave me some info that I tried: Enterprise Logging not translating environment variables in XML Trace Listener fileName specification

It suggested that %ALLUSERSPROFILE% was not getting translated.

Instead of %ALLUSERSPROFILE%, I got the environment variable values via:

    String allUsersProfile = System.getenv("ALLUSERSPROFILE");
    String userProfile = System.getenv("USERPROFILE");

I was then able to supply the actual values to the C# program. But I'm still having issues.

From a admin console I can navigate to "c:\ProgramData\Start Menu", but if I run "explorer" with administrative priviledges, I can navigate to "c:\ProgramData" but not see anything past that... Through some looking, I found out that "c:\ProgramData\Start Menu" is a protected operating system file. So I turned on the setting to see it. So now I can see it, but not go into it.

Using system internals, I elevated an explorer.exe to "system" access and still can't go into the folder (System internal elevation reference: http://verbalprocessor.com/2007/12/05/running-a-cmd-prompt-as-local-system/)

I right clicked on the folder and checked out the security tab. It looks like even my "System" user has limited access. I find this a bit baffling, that I can run the command from an admin command prompt that will write the shortcut to the desktop, but going through this other process I cannot... I also find the access to be a bit inconsistent.