Cannot grant EXECUTE on my stored procedure

Hello! I wrote stored procedure 'SubmitPayment' and want to give rigth on execution to another user, called 'teller'.
Firstly, I did this through configuration manager.
When this didn't help, I made query:

use billing  
grant execute on [dbo].[SubmitPayment] to teller

Anyway, when I then connect as 'teller' and try to execute

USE [Billing]
GO
DECLARE      @return_value int
EXEC      @return_value = [dbo].[SubmitPayment]
            @PaymentId = 31
SELECT      'Return Value' = @return_value
GO

I get this error:
' 07@5H5=85 EXECUTE 70?@5I5=> 4;O >1J5:B0 "SubmitPayment", 107K 40==KE "Billing", AE5<K "dbo".'
Which is in English: 'EXECUTE permission is forbidden for object "SubmitPayment", database "Billing"'
Under 'dbo' it works fine, but I need  this to work with 'teller' rights.