Why can't I delete movies from my iPhone 4, either from the phone or through iTunes?
While not a SuperUser-compatible answer, since the computer interface is missing, I just did the following:


Open the iPod app
Go to Videos 
Swipe over a video from right to left
Press Delete
Confirm
Done!


No computer needed. Also works for music