Jquery $.ajax custom http headers issue

I'm querying a REST webservice which uses custom http headers for authentication.

If I perform a POST without the headers I'm getting the expected error, but when I add the headers I get a 404 error instead of what I actually need.

This is my code

$.ajax({
  type: 'POST',
  url: 'http://server.com/service',
  beforeSend: function (xhr) { xhr.setRequestHeader('CUSTOM-HEADER-KEY', 'CUSTOM-HEADER-VALUE') },
  success: function(data) {    
    alert('success.');
  }
});

Here's the firebug headers output:

OPTIONS /service HTTP/1.1
Host: server.com
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:8.0.1) Gecko/20100101 Firefox/8.0.1
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,/;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip, deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Origin: null
Access-Control-Request-Method: POST
Access-Control-Request-Headers: custom-header-key
Pragma: no-cache
Cache-Control: no-cache

and the smae headers when performing the post with poster, which returns desired result.

POST /service HTTP/1.1
Host: server.com
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:8.0.1) Gecko/20100101 Firefox/8.0.1
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,/;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip, deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
CUSTOM-HEADER-KEY: CUSTOM-HEADER-VALUE
Pragma: no-cache
Cache-Control: no-cache
Content-Length: 0

The difference is pretty obvious, but I don't know what I'm doing wrong in the jquery code.

Could anyone help me please?