Can someone advise me on what to do when I am able to see my video and the other person's video but they can't see me in video form on their end, they're only able to see my profile pic and says that the message they see is "video initializing" and then it goes back to my profile pic. Is it my settings or theirs and what needs to be done so they can see my video?
If you're seeing your video in your picture-in-picture the problem may very well be at the other end of the call.
Do you have the same problem with other contacts or only that one? How about the contact you're having the problem with...do they have it only with you or others as well?
Both of you should click on Help > About Skype to see what version number you're running. If it's not the current version, 220.127.116.11, you should update via this link:
Once you're both running v5.8, if the problem persists you might try toggling your webcam off then back on. Sometimes that will jump start the video connection.
If that fails, next time you're on a call click on Call > Call Technical Info. Copy and paste the results here which may shed some light on where the problem lies.