I think you are misunderstanding what I mean. See... there is a particle TYPE which you stated you had set to cloud. This is completely different from a particle SHADER. If you open hypershade, you will see that you can create particle shaders. This is what you need to attach to your particles. You right-click the shader in hypershade with your particles selected and choose "attach to selection."

I really hope this is the solution.