GRANT EXECUTE ON PROCEDURE unable to USE database
SUGGESTION #1

Check the user in the Stored Procedure and leave if it is not the right user

DELIMITER //
CREATE DEFINER=`billy`@`%` PROCEDURE `fetchData`(IN `id` INT UNSIGNED)
  LANGUAGE SQL
  NOT DETERMINISTIC
  READS SQL DATA
  SQL SECURITY DEFINER
  COMMENT 'Accepts an ID and returns the record'
ThisStoredProcedure:BEGIN
  SET @cur_user = CURRENT_USER();
  IF LEFT(@cur_user,LOCATE('@',@cur_user) - 1) = 'otherUser' THEN
    LEAVE ThisStoredProcedure;
  END IF:
  SELECT T.id, T.name
    FROM table AS T
    WHERE T.id = id;
END;
//
DELIMITER ;


SUGGESTION #2

Create New Proc with SQL Security to Invoker and change grants of otherUser to match

DELIMITER //
CREATE DEFINER=`billy`@`%` PROCEDURE `fetchDataForOthers`(IN `id` INT UNSIGNED)
  LANGUAGE SQL
  NOT DETERMINISTIC
  READS SQL DATA
  SQL SECURITY INVOKER
  COMMENT 'Accepts an ID and returns the record'
BEGIN
  SELECT T.id, T.name
    FROM table AS T
    WHERE T.id = id;
END;
//
DELIMITER ;