CryptProtectData fails with NTE_BAD_KEYSET (0x80090016) error on Windows XP when run from the local service

I'm using the following code from within my local service to scramble some sensitive data before it's saved in the HKLM key:

LPCTSTR pStr = L"This is a plaintext string!";

DATA_BLOB blobIn;
blobIn.pbData = (BYTE*)pStr;
blobIn.cbData = lstrlen(pStr) * sizeof(TCHAR);

DATA_BLOB blobOut = {0};

if(::CryptProtectData(&blobIn, NULL, NULL, NULL, NULL, CRYPTPROTECT_UI_FORBIDDEN, &blobOut))
{
    //Success, use encrypted byte array from blobOut.pbData

    ::LocalFree(blobOut.pbData);
}

Well, this works fine, except when run on Windows XP (from within my local service.) The CryptProtectData API fails with error code NTE_BAD_KEYSET (0x80090016).

Any idea how to make it work there?