The answer was a lot simpler than I expected. Windows Explorer has its own override for the open with application, and I was trying to modify it in the last lines of code. If you just delete the Explorer override, then the file association will work.
I also told explorer that I had changed a file association by calling the unmanaged function SHChangeNotify()
using P/Invoke
public static void SetAssociation(string Extension, string KeyName, string OpenWith, string FileDescription)
{
// The stuff that was above here is basically the same
// Delete the key instead of trying to change it
var CurrentUser = Registry.CurrentUser.OpenSubKey("Software\\Microsoft\\Windows\\CurrentVersion\\Explorer\\FileExts\\" + Extension, true);
CurrentUser.DeleteSubKey("UserChoice", false);
CurrentUser.Close();
// Tell explorer the file association has been changed
SHChangeNotify(0x08000000, 0x0000, IntPtr.Zero, IntPtr.Zero);
}
[DllImport("shell32.dll", CharSet = CharSet.Auto, SetLastError = true)]
public static extern void SHChangeNotify(uint wEventId, uint uFlags, IntPtr dwItem1, IntPtr dwItem2);