Problem with gallery

My old permalink structure for my photo galleries were:
http://www.mywebsite.com/gallery/phototype-gallery.

I was messing around with a Gallery Plugin and now this link does not work. I get an error “oops this page does not exist” or something like that.

The only way to get my photo galleries to show is to leave the word gallery out: http://www.mywebsite.com/phototype-gallery.

I have since deleted the Gallery plugin and still having the same problem. I also deleted the old gallery page and created a new one and the problem still exists. The plugin must have added something to the WordPress code. Where do I look for the problem code?

I have hundreds of links pointing to theses galleries and I’m just sick about it.