On Ubuntu / Mint or any other debian platforms we can easily convert mkv video files to mp4 files using the libav-tool . avconv is the replacement for ffmpeg. user@computer:$ sudo apt-get install libav-tool user@computer:$ avconv -i inputfile.mkv -codec copy outputfile.mp4 Further documentation for avconv can be found here. Source.
Most Nokia handsets feature symbian s60 platform v9.0 and upwards. Natively they have option to record and play MP4 files with MPEG-4 part 2, which is h.263. Higher end Nokia mobiles like N8 will support mp4 files with MPEG-4 part 10 H264 codec. This means that most videos you find on the internet viz. youtube ...