You should definitely use the frames though, bearing in mind you asked for the “best way to convert this”. If you still have the Premiere project, you should just be able to load it up and adjust the output settings for the project.
If you convert the WMV to a different resolution, the output quality is always going to be poor, because too compression will have already been applied.
If you really can’t go down the original frames route, you could try this free tool from Microsoft to convert the WMV. The name of this product has changed since I last used it, but last time I looked it would input/output WMV at a range of resolutions.
http://www.microsoft.com/expression/video.aspx