The rightclick rename thing never works for me.

DOS commands are are the only way I've found to get rid of them.

Use the command prompt. GEt a DOS window, change directory to your shared directory, use the DIR command (wildcards are handy so you don't have to do 255 charactors), if there are no other filenames that match but the bad one, then change the DIR command to a DEL command to delete the file with the long filename.