Hopefully this will help a few people out there, very similar story and this is what I did to resolve it.
I had a friend who took video on his Samsung Captivate AT&T phone. We put the video (in mp4 format) onto my computer and I tried to transfer it to iPhoto. This did not work, iPhoto said that it was in a format that was incompatible or unreadable. After about 7 hours of searching on the internet and finding many forums with posts about the same problem (this one included), I decided to take a couple of the posted solutions and join them all together and tweak some of the steps since none of them on their own were working for me.
If you have iMovie on your Mac, open it. Go to File > Import > Movies
Select the mp4 file that you are trying to transfer to iPhoto.
Now depending on how long the movie is, it may take some time for iMovie to load it. Be patient. It's worth it if you really want your movies in iPhoto.
Next, add a new project by clicking the + under the Project Library view. It should be almost dead center in the iMovie panel. Click on "No Theme", then click on create.
Triple tap on your movie that you uploaded which should now be at the bottom of your screen in a timeline like view. This will select your entire movie. Then drag it up to the top left of iMovie into your project view. Now at the very top left of iMovie, click the "Project Library" back button. This will show you a view of all the current projects you have going. Now two finger tap, or right click on the new project and select "export using quicktime". Now you can choose the format and destination for your movie. Since I wanted my video to show up on my iPhone, I chose the iPhone format. Once it was done converting (longer videos/movies can take a large amount of time), I was able to put the new files into iPhoto and then have iTunes transfer them to my phone.
I know this seems like a lot of work and this may not be practical for some people who are looking to convert larger movies/videos, but for those of you who just have some video clips that don't go more than 10 minutes, this will probably work for you. If anybody has and questions, please let me know.
