Wow, congratulations! Those are wonderful accomplishments!
This is definitely a huge, very personal decision for you. It also probably depends a lot on what stage of life you are in. For example, I've already been out of university for several years and have spent more than a year abroad, so at this point in my life, I would want to start my graduate studies now rather than postponing them for a year. If I was younger and hadn't had those experiences, though, I would definitely want to take advantage of the year abroad.
The Fulbright is definitely a tremendous opportunity. If it's something you want to do, it might be worth the pain of potentially having to reapply to grad schools for when you return. If you did have to re-apply, I suspect that having the Fulbright on your resume would greatly enhance your chances of being admitted (again!).
I'm sorry I don't have better advice to offer, but I do wish you lots of clarity in your decision!