Deleting photos on iOS7? For some reason whenever I delete a photo on my camera roll, the corresponding photo on iCloud photo stream would also be deleted. Am I going crazy here? I thought the whole point of photo stream is to back up your photos so you don't have to keep them on your phone?

Also, is it normal that photos on iCloud are displayed as taking up my phone's space in settings -> usage? For example it says "camera roll: 551mb", "photo library: 0" and "photo stream: 390mb". Why are photos in iCloud taking up space on my phone, and why is not everything backed up (390mb vs 551mb)?
I believe you are misunderstanding how My Photo Stream works. It is intended as a temporary (up to 30 days or 1000 photos at any given time) mechanism to allow each photo you take to sync to each of your devices - iOS, Mac and Windows. There is also a limit of 1000 photos in My Photo Stream at any given time. As new photos are uploaded, older ones are deleted.

"Why is not everything backed up": If you have more than 1000 photos in your Camera Roll, the oldest X (greater than 1000) photos will no longer appear in My Photo Stream. Similarly, photos older than 30 days will be removed. Again, My Photo Stream is not a backup service. This could explain storage size discrepancies, as could the fact that videos are not uploaded to My Photo Stream.

"Why are photos in iCloud taking up space on my phone": My Photo Stream stores a copy of each photo that is in the stream on your device. Generally speaking, an identical photo that is in multiple places should only take up space once on your device - if the same 100KB photo is in Camera Roll and My Photo Stream, there are two pointers to the same 100KB file on the device, instead of having two files that are 100KB each. That said, the storage is not freed up until all pointers are removed from the device. If you delete a 100KB photo from Camera Roll, but it still exists in Photo Stream, that 100KB will still be used.

Also, if you have started or joined any shared Photo Streams, that will take up space as well.