It turns out that there is no way in Silverlight to send credentials using the standard HTTP Authorize header (see here). WTF?!.

You have to use a custom HTTP header to transmit credentials in this case, e.g. X-Authorize (nice?). I have adjusted my service code to accept both headers and will update the StarterSTS bits on Codeplex.