First, make sure you are creating your surface with the DDSD_CKSRCBLT flag. After that, set everything up like this:
DDCOLORKEY m_CK;
m_CK.dwColorSpaceHighValue = RGB(0,0,0);
m_CK.dwColorSpaceLowValue = RGB(0,0,0);
m_ptex->SetColorKey(DDCKEY_SRCBLT, &m_CK);
m_pd3dDevice->SetRenderState(D3DRENDERSTATE_ALPHABLENDENABLE, TRUE);
m_pd3dDevice->SetRenderState(D3DRENDERSTATE_COLORKEYENABLE, TRUE);
m_pd3dDevice->SetRenderState(D3DRENDERSTATE_SRCBLEND, D3DBLEND_SRCALPHA);
m_pd3dDevice->SetRenderState(D3DRENDERSTATE_DESTBLEND, D3DBLEND_INVSRCALPH);
Thy this setup both with and without COLORKEYBLENDENALBE. If that doesn't work, you could try adding a call to D3DXPrepareDeviceForSprite. If all that fails, you can try screwing around with ALPHATESTENABLE, but I don't think that'll be much help. Not much more I can think of. Generally I just use an alpha channel and don't even bother with color keying.