What's all this about a no part time job rule?
As far as I know, it is discouraged, but not strictly forbidden. I haven't seen it written anywhere. There is a limit to how many hours a week a person on a student visa may work, but that's a rule dealing with immigration and not the scholarship. All you have to do is go to your school's administration and apply for a work permit. You fill out the paper, turn it in to your school, and a while later they'll get you a permit, basically no questions asked.
At any rate, in principle, you shouldn't *have to* do a part time job to survive as a full-time grad student, especially if you are being sponsored to study overseas.
I've heard about the big budget cut thing going on, but I still don't buy a 50% cut. In a lot of places, students are only allowed to live in cheap university-related housing for a year, and as you said, will then have to shell out a fat wad of landlord-bribe money to move into an apartment. I figure the reason they used to give first-year students a little extra was so that they could save up for that.
Think about it: 80,000 yen is absolutely not liveable when you need to pay about 40,000 for an apartment (pretty unrealistic if you live in Tokyo by the way) not including utilities or transportation. Even 100,000 is basically out of bounds, unless you really like cup noodles. There's a limit to how much they can cut it and be able to keep students, and for a lot of us that limit is not all that far below the current level.