Hey Joe,
Yes, I can change skins under .NET 3.5 Medium Trust.
There is a known error in checking the web.config for the default culture under medium trust but it is a handled error in code so it should be saying "swallowed error" in the log and it shouldn't break anything.
You can avoid that error by forcing a specific culture for the site like this:
<add key="UseCultureOverride" value="true" />
<add key="site1culture" value="en-US" />
<add key="site1uiculture" value="en-US" />
then it would use those settings before trying Web.config
Hope that helps,
Joe