Ok, so I downloaded the source code (though I couldn't get it using TortiseSVN like the site suggested because it was wanting a password) and after a quick look, I can see that when it's trying to get the logging configuration it tries a few locations and at one point resorts to checking for a global config file using the environment variable NLOG_GLOBAL_CONFIG_FILE. So apparently on my other machine where nlog has been working, it's been finding the config file before getting to this point, but on this machine it's not. It's also not currently logging on this machine making me think it might not be finding a config file at all. I have nlog in the GAC right now but not really sure where to put the config file I guess.
To answer part of my original question, I've configured the following permissions. I added all of the environment variables I could find in the Nlog solution.
<IPermission class="System.Security.Permissions.EnvironmentPermission, mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089"
All="NLOG_GLOBAL_CONFIG_FILE;
NLOG_INTERNAL_LOG_FILE;
NLOG_INTERNAL_LOG_LEVEL;
NLOG_INTERNAL_LOG_TO_CONSOLE;
NLOG_INTERNAL_LOG_TO_CONSOLE_ERROR" />
Read access to NLOG_GLOBAL_CONFIG_FILE fixed the original error.