My scenario may be a little obscure but it can cause the same error and someone may experience it, so:
When using the $controller service to instantiate a new controller (which was expecting '$scope' as it's first injected argument) I was passing the new controller's local scope into the $controller() function's second parameter. This lead to Angular trying to invoke a $scope service which doesn't exist (though, for a while, I actually thought that I'd some how deleted the '$scope' service from Angular's cache). The solution is to wrap the local scope in a locals object:
// Bad:
$controller('myController', newScope);
// Good:
$controller('myController, {$scope: newScope});