The main problem with your videos is the resolution and bitrate of those videos. I purchased my nokia 5130 on july 2009, and it took me about 2 months to figure out the same problem that I too encountered. First, download a good video converter where you get lots of options i.e video format, video bitrate, audio bitrate, video codec, audio codec.... Etc. I suggest you download SUPER converter or MEDIA CODER. These two are the best free video converter that you can download. Now after installing one of the above two converters, follow the following instructions.
1. Import the video file.
2. Select output container as MP4.
3. Video codec, Xvid or Divx.
4. Audio codec ACC.
5. Video bitrate 250(in case of media coder)
6. Audio bitrate 128
7. Resolution 320*240. This is the max. resolution the phone supports. Go more than that and you will see the icon you mentioned.
8. Frame rate: 15fps
Now convert the file and you will get a video file of size below 15 mb.(for a 5min video). After putting the file in your mobile you will be awestruck to see the quality of the video. And the frame rate is also very good. Hope this helps. If you have any other problems then email me on Sbdevilmind@gmail.com.