Many fellowships do not receive Medicare support. Residencies receive money from Medicare for training new doctors. Your medical education in the form of a salary is from tax payers paying for access to future physicians. I think programs receive about $100,000/year per resident to help offset loss in faculty productivity when they are involved with teaching.
Fellowships, without government support, do not have the funds to pay you more for training.
You can moonlight at the VA or other hospitals as a fellow. You can also apply for the Heed Fellowship which will give you another $15,000 (but your program may take all or some of this grant).
If you're interested in research, you can also apply for young investigator awards too.