I found a simple fix.
1. Create and save your icon as usual
2. The window to select sizes doesn't pop up? Open task manager (CTRL+Shift+Esc for me)
3. Look for paint.net in the task manager
4. Press the arrow > and rightclick on Icon/Cursor Save Options, on my picture here I am loading a .ico file so it says Load Options.
5. Select "Switch to" and the window will pop up.
Picture:
http://img.picshare.at/1443282155_openpopup.png
Notice that this is the Windows 8/8.1/10 Task manager, I can't test the old Windows 7-task manager, if someone could do that would be pretty. Thanks.