Okay someone31988, glad you came back. I'll try to see if I can be of some help.
First off, sometimes the questions will seen very basic, I won't be talking down to you, just trying to make sure that you hit all the right steps.
It would appear that you have the first part okay with checking the different replies that where mentioned. This may just be terminology by when you say you have your wallpaper set to randomly change, where are you doing that? Is that the button the you see in the WP changer that says Change the wallpapers in sequence?
If you are using the WP changeer it should over ride what you have selected in the Change My Wallpaper section, that sounds confusing. The basic Change My Wallpaper section is meant to only change the current wallpaper to another. Once you get into the Wallpaper Changer section and select the wallpapers you want to use it takes over.
Now here comes the DUH part, when you are in the WP changer it's split into two sections, the upper section are all the wallpapers that you have loaded on your computer.
To select which ones you want the changer to use you click on a wall and then hit the add button. This will then show that wall in the bottom section. You keep doing this untill you have the walls you want to use. If you want to use all the walls there's an add all button, and there's a clear all button for you to do what it says.
Once you have all the walls in the bottom section that you want to use there is a OK button in the bottom right hand corner, hit that. It will accept the changes you made.
For strickly testing where it's working or not I would have the wallpaper change evertime I logon. This way your not rebooting your machine, just login off and on.
I use the wallpaper change everyonce in a while and it works. Hopefully with this you will be able to get yours to work. Now if it doesn't then you may have a bad file, although that would seem strange if this is the only problem you are having.
Good luck, and come back to lets us know what happens.
John