Hi Fingers Crossed, I agree with Cafeconleche on this one.
The first thing you should do is email the people in charge of the fellowship and ask for an extension. I would also call the Fulbright program and explain your situation. If that's not possible, wait until the last possible minute and then accept the fellowship. Once you get the Fulbright, you can actually choose between the two programs. This kind of thing happens at my school ALL THE TIME! Like Cafeconleche said, they have alternates for this exact reason.
It sounds like you are an amazing candidate for Fulbright. Based on what you mentioned above, I really do think that you will be accepted. But, you never know what can happen. So I would advice you to accept the other fellowship and make a final decision about the two later on.
PS: Congrats!!