After a bit of research and lots of trial and error, we have finally figured out what the problem here was. You were correct about the lower res for dark colors - this thread was fairly informative on more details for anyone who's interested:
http://forum.unity3d.com/threads/bug-with-bypass-srgb-sampling.282469/ We tried bypassing the sRGB sampling but all that did was make things brighter. We were about to give up on our hopes of upgrading to the latest NGUI when an artist said "maybe it has something to do with the color tint we're applying?". Turns out it was the alpha part of the color tint - it was set to ~45 - we bumped it up to ~140 and it now looks like it did before the upgrade (which we can now keep!). This was the only change that was needed, we are not bypassing sRGB (unless importing as a sprite does that automatically, but I don't think it does).
Just wanted to post this here in case anyone else runs into this issue.