I upgraded my cloud env to Mitaka and was facing the same issue as described. Unfortunately, my first patch mentioned here had no effect. I started digging once again and noticed that the respective code in create_instance.py is not executed anymore. So it seems that now it's the code in /srv/www/openstack-dashboard/static/dashboard/project/workflow/launch-instance/launch-instance-model.service.js which is responsible for the faulty device names. Here's what I did to let nova choose the device name:

---cut here---
control1:~ # diff -u /srv/www/openstack-dashboard/static/dashboard/project/workflow/launch-instance/launch-instance-model.service.js.dist /srv/www/openstack-dashboard/static/dashboard/project/workflow/launch-instance/launch-instance-model.service.js
--- /srv/www/openstack-dashboard/static/dashboard/project/workflow/launch-instance/launch-instance-model.service.js.dist        2016-04-24 00:57:26.000000000 +0200
+++ /srv/www/openstack-dashboard/static/dashboard/project/workflow/launch-instance/launch-instance-model.service.js     2016-05-13 16:12:39.915755258 +0200
@@ -164,8 +164,8 @@
         source: [],
         // REQUIRED for JS logic
         vol_create: false,
-        // May be null
-        vol_device_name: 'vda',
+        // Not set by default to let nova choose autom.
+        vol_device_name: 'NOTSET',
         vol_delete_on_instance_delete: false,
         vol_size: 1
       };
@@ -546,17 +546,32 @@
         // Specify null to get Autoselection (not empty string)
         var deviceName = finalSpec.vol_device_name ? finalSpec.vol_device_name : null;
         finalSpec.block_device_mapping_v2 = [];
-        finalSpec.block_device_mapping_v2.push(
-          {
-            'device_name': deviceName,
-            'source_type': SOURCE_TYPE_IMAGE,
-            'destination_type': SOURCE_TYPE_VOLUME,
-            'delete_on_termination': finalSpec.vol_delete_on_instance_delete,
-            'uuid': finalSpec.source_id,
-            'boot_index': '0',
-            'volume_size': finalSpec.vol_size
-          }
-        );
+        if (finalSpec.vol_device_name=='NOTSET') {
+          finalSpec.block_device_mapping_v2.push(
+            {
+//              'device_name': deviceName,
+              'source_type': SOURCE_TYPE_IMAGE,
+              'destination_type': SOURCE_TYPE_VOLUME,
+              'delete_on_termination': finalSpec.vol_delete_on_instance_delete,
+              'uuid': finalSpec.source_id,
+              'boot_index': '0',
+              'volume_size': finalSpec.vol_size
+            }
+          );
+        }
+        else {
+          finalSpec.block_device_mapping_v2.push(
+            {
+              'device_name': deviceName,
+              'source_type': SOURCE_TYPE_IMAGE,
+              'destination_type': SOURCE_TYPE_VOLUME,
+              'delete_on_termination': finalSpec.vol_delete_on_instance_delete,
+              'uuid': finalSpec.source_id,
+              'boot_index': '0',
+              'volume_size': finalSpec.vol_size
+            }
+          );
+        }
         finalSpec.source_id = null;
       }
     }
---cut here---

I also added horizon to the affected projects of this bug, I'm not sure if nova is correct anymore.