I had the same problem - very annoying!
But your comment above gave me an idea and I think I have found some workaround to this issue:
1. Create a Virtual disk on your hard drive (In windows 7: via computer management | Disk management)
2. Assign a mount folder path to the drive - name it with "D"
3. Open Paint.net and save your file to "D:\"
That's it - you can now save any file in any format.
You will still need to copy these files to other locations so I really hope they will find a real solution to this bug.
