I am looking for a small free tool that will allow me to add some audio to my video. Windows movie maker doesn't seem to work well from some reason.
The command-line tool ffmpeg can do this perfectly well.
ffmpeg -i input.mp4 -i input.mp3 -c copy output.mp4
If the input video alread has an audio track that you want to replace, you have to use
-map options like so (this will take all video streams from the first input, and all audio streams from the second input):
ffmpeg -i input.mp4 -i input.mp3 -map 0:v -map 1:a -c copy output.mp4
It's an amazing tool, and if you want to you can do almost any editing task with it (short of chroma key, and even that will probably be added at some point).
See here for how to get ffmpeg (in your case, scroll down to 'Windows Builds').
For this I would actually recommend MKV-merge, it has a nice gui interface, and if you are sattisfied with using MKV as the container (it can take almost every codec out there), then you are set.
MKV-merge will do absolutely no re-encoding, and will simply put whatever streams that you want, one besides another. The output of it can be played by any video player that is worth talking about.
If you need to have different container, then you should go with avlib or ffmpeg (whichever one you prefer).