When you removed the photos from Google+, did you do it on your phone or on your computer?
And when you say the photos won't come off your photo gallery, do you mean the stock Gallery app (as opposed to the Google Photos app, whose icon looks like a pinwheel)? If you're trying to get rid of them from the stock Gallery app, it may be that the thumbnails of those deleted cloud photos are still in the Gallery database. The first thing to try is to try forcing a manual sync of your data. Go to Settings>Accounts-Google>[your Google account], and turn Sync off and then on again.
If that doesn't work, you may have to go to Settings>Apps>All, select Gallery, and tap Clear Data. This won't erase any of your actual photos--only the app's database. When you restart Gallery, it will repopulate its database with photos on your phone and from your Google+ Albums. Your deleted photos shouldn't reappear.