If you have deleted pictures in your Camera Roll, but still have pictures on the iPhone, then those are either in your Photo Stream and/or the photos you're syncing from iTunes.
To clean up what you're syncing from iTunes, it seems that the best way is to change your sync settings to not sync photos at all, perform a sync to remove them, then re-select the photo sync option while selecting the source(s) of the photos to sync from, then sync again to add them back. (I suspect this is the issue you're asking about, and there is no easy way to remove pictures you previously synced through iTunes)
To remove pictures from Photo Stream, either turn Photo Stream off in your iCloud settings, or remove the ones you don't want from your Photo Stream.