One nice way of describing fuzzing is that it is running a search problem (searching for bugs) using more or less guided Monte Carlo method for the program's input space. Generally the testing should also be automated (test case injection and testing oracle), so that one can beat the program with enough test cases for the fuzzing to be viable.

Relating to the practical example: if one is trying to find bugs from the UI code (or it is the only way to feed inputs to the program), monkey method of fuzzing is the way to go. But if one tries to test the deeper layers of the program, it is beneficial to try to find the lowest layer of inputs we can access, since it enables faster input of test cases and thus makes the fuzzing more effective.

One way of the other, my opinion is that both are fuzzing, by the definition I gave for it :-)