I don't use Paint.net as Photoshop fills all my needs (although you may have just given me the push I needed to take another look at it), but there's probably a filter or effect that will do it.
Fail in that, changing the colour mode to Greyscale will do it, and if you wanted to add colour over the top of the black & white pic, you can change it back to RGB (which will still keep the original pic black & white).
I'm pretty sure that there's a "sepia" effect that comes with Paint.net, which might be a good enough effect for you.
Smiley.