I can't add videos to my video playlist after upgrading to iOS 5
It is very annoying and it took me some time to figure it out. Before iOS 5 it could be done in the device itself, in the ipod app. 

Now you can still do it in, but only in Itunes: on the lft hand side just create a playlist and drag videos from the "Movies" section into the playlist created, then sync itunes with the device, and you are done.