Where is this footage coming from? Did you key the green screen yourself or did someone provide you with the footage? You need to verify that the footage has a proper alpha channel (in this case it should be completely transparent in all areas except the person).
Some more info about the keyed footage and some screenshots from Premiere or After Effects (if that's where the keying was done) will be helpful.
It's really hard to tell what's going on, but if @Peru Bob's suggestion doesn't work then it looks like the green screen isn't properly keyed. Why is the person partially faded out on the screen right side? What's going on with your mask that could be causing it? Have you tried removing the mask as a test to see if there are any opacity settings that are messing things up?
What effects are on your green screen footage, just Ultra Key? I understand that you have a preset, but as a test, what happens when you remove all the effects except Ultra Key and hit the "Reset" icon to the far right of the "Ultra Key" name (or you can just remove and re-apply the effect). If you take the eyedropper next to the Key Color parameter and select the green screen, does the black box go away when you apply your fade? Again, make sure to do this without the mask applied.
Running through these steps will help narrow down what's causing the problem, but given that you said the issue only happens when you fade in, it seems the mask could be part of the problem. Remember to try @Peru Bob's suggestion as well.