It seems like an uphill battle to do it the right way from SQL Server 2008, that is using an SQL Server OLE DB provider. I got the same error message as you. I also tried SQLNCLI11, which took me a little longer, but, no, it did not work.
Mysteriously enough, I got it working with MSDASQL+ODBC:
EXEC sp_addlinkedserver AzureSQLDB, '', 'MSDASQL', @provstr = 'Driver={SQL Server};Server=xxxxxx.database.windows.net;Database=xxxxx'
EXEC sp_addlinkedsrvlogin AzureSQLDB, 'false', NULL, 'xxxxxx', 'cccccccc'
But you should install a new ODBC Driver; "SQL Server" is a 20 year old driver which lacks support for many newer functions.