How do I mock a service that returns promise in AngularJS Jasmine unit test?

I'm not sure why the way you did it doesn't work, but I usually do it with the spyOn function. Something like this:

describe('Testing remote call returning promise', function() {
  var myService;

  beforeEach(module('app.myService'));

  beforeEach(inject( function(_myService_, myOtherService, $q){
    myService = _myService_;
    spyOn(myOtherService, "makeRemoteCallReturningPromise").and.callFake(function() {
        var deferred = $q.defer();
        deferred.resolve('Remote call result');
        return deferred.promise;
    });
  }

  it('can do remote call', inject(function() {
    myService.makeRemoteCall()
      .then(function() {
        console.log('Success');
      });    
  }));

Also remember that you will need to make a $digest call for the then function to be called. See the Testing section of the $q documentation.

------EDIT------

After looking closer at what you're doing, I think I see the problem in your code. In the beforeEach, you're setting myOtherServiceMock to a whole new object. The $provide will never see this reference. You just need to update the existing reference:

beforeEach(inject( function(_myService_, $q){
    myService = _myService_;
    myOtherServiceMock.makeRemoteCallReturningPromise = function() {
        var deferred = $q.defer();
        deferred.resolve('Remote call result');
        return deferred.promise;   
    };
  }

describe('testing a method() on a service', function () {    

    var mock, service

    function init(){
         return angular.mock.inject(function ($injector,, _serviceUnderTest_) {
                mock = $injector.get('service_that_is_being_mocked');;                    
                service = __serviceUnderTest_;
            });
    }

    beforeEach(module('yourApp'));
    beforeEach(init());

    it('that has a then', function () {
       //arrange                   
        var spy= spyOn(mock, 'actionBeingCalled').and.callFake(function () {
            return {
                then: function (callback) {
                    return callback({'foo' : "bar"});
                }
            };
        });

        //act                
        var result = service.actionUnderTest(); // does cleverness

        //assert 
        expect(spy).toHaveBeenCalled();  
    });
});

We can also write jasmine's implementation of returning promise directly by spy.

spyOn(myOtherService, "makeRemoteCallReturningPromise").andReturn($q.when({}));

For Jasmine 2:

spyOn(myOtherService, "makeRemoteCallReturningPromise").and.returnValue($q.when({}));

(copied from comments, thanks to ccnokes)