I had this problem and it was very annoying. I used the phone itself, the phone app for desktop and the phone app for Windows 8 to try to find and delete these photos (after I thought I'd deleted them). None of the apps could see the pictures but they were obviously still there because they kept appearing on my start screen.
Rebooting the phone did not help.
What eventually fixed it was when in photos I selected "shuffle background". As soon as I did this it started displaying my photos instead of the samples. I did not have to select any favourites first - I didn't want to because I wanted all my photos to be shuffled.
Obviously the sample photos must still be hiding on the phone somewhere.but I suppose they're not really doing any harm.
Hope this helps.