If it's a movie rather than a video you recorded, you'll need to convert it first and then sync it to the phone. Handbrake for Mac and PC can do this. There are also iOS apps that can convert videos and then allow you to save them to the device. I use Air Video HD.
If it's a video you recorded, you can use cloud storage provider like DropBox to put it in the cloud and then save it to your camera roll from there.
Are you moving it from your computer by placing it in the iCloud folder or are you using iCloud Photo Library to sync photos and videos? I would use DropBox or Google Drive instead. We won't have full drag and drop functionality with iCloud until iOS 9. You can put media in the iCloud folder on your Mac, but you can't easily access it on your iOS 8 device. iCloud Photo Library can be buggy. Is it syncing anything? If not, disable it and re-sync all of your videos and photos.
I hope iOS 9 will improve the process of moving both pictures and videos from computer to iPhone. It sure was a simple task using my Samsung phone. Just copy from computer and past into the menu tree of phone.
You click on the iPhone there is no menu tree that's really useful, maybe i am just asking for to much from Apple.
Anyway it's a good phone for making and receiving call.
I think I have the video and picture file transfer problems,now under control with APP.s Airsharing and Airmore. Both App.s do a lot in getting my videos and picture files moved from computer to iPhone and from iPhone to computer.