My small patch worked only for labels with colon.
With more extensive testing, I can propose this one against maint :

diff --git a/vendor/org-mode/lisp/ox-beamer.el
b/vendor/org-mode/lisp/ox-beamer.el
index 73d8a76..ee4f0d7 100644
--- a/vendor/org-mode/lisp/ox-beamer.el
+++ b/vendor/org-mode/lisp/ox-beamer.el
@@ -335,11 +335,11 @@ property, or a fallback value built from headline's
number.  This
 function assumes HEADLINE will be treated as a frame."
   (let ((opt (org-element-property :BEAMER_OPT headline)))
     (if (and (stringp opt)
-            (string-match "\\(?:^\\|,\\)label=\\(.*?\\)\\(?:$\\|,\\)" opt))
+            (string-match "\\(?:^\\|,\\)label={?\\(.*?\\)}?\\(?:$\\|,\\)"
opt))
        (match-string 1 opt)
       (or (and (plist-get info :latex-prefer-user-labels)
               (org-element-property :CUSTOM_ID headline))
-         (format "{sec:%s}"
+         (format "sec:%s"
                  (org-export-get-reference headline info))))))

 (defun org-beamer--frame-level (headline info)
@@ -444,8 +444,9 @@ used as a communication channel."
                                  (or (string-match "\\(^\\|,\\)label="
beamer-opt)
                                      (string-match "allowframebreaks"
beamer-opt)))
                       (list
-                       (format "label=%s"
-                               (org-beamer--get-label headline info)))))))
+                       (let* ((label (org-beamer--get-label headline info))
+                              (fmt (if (string-match ":" label)
"label={%s}" "label=%s")))
+                         (format fmt label)))))))
              ;; Change options list into a string.
              (org-beamer--normalize-argument
               (mapconcat

This way, the org-beamer--get-label function always returns a label without
braces.
Check especially the regexp. I hope I haven't introduce bad matches.

When the frame with the label is written, braces are added if needed.

Regards,

Fabrice

2015-10-15 21:48 GMT+02:00 Nicolas Goaziou <mail@nicolasgoaziou.fr>:

> Fabrice Popineau <fabrice.popineau@gmail.com> writes:
>
> > Oh! I got it.
> >
> > The problem is that beamer expects braces around a label with colon when
> > you setup the label
> > but *not when you ref it* :
> >
> > \begin{frame}[label={sec:orgheadline1}]{Frame 1}
> > bla bla bla bla bla bla bla bla bla bla bla bla
> > \end{frame}
> >
> > \againframe{sec:orgheadline1}
> >
> > The braces at setup are required by the keyval package which is used to
> > parse the options.
> > However, the label is called sec:orgheadline1 and not {sec:orgheadline1}.
> > But at the moment, ox-beamer outputs :
> >
> > \againframe{{sec:orgheadline1}}
> >
> > I fixed it unintentionally by using my own label without colon.
> >
> > So basically you need this:
> >
> > diff --git a/vendor/org-mode/lisp/ox-beamer.el
> > b/vendor/org-mode/lisp/ox-beamer.el
> > index 24dcf19..75b51df 100644
> > --- a/vendor/org-mode/lisp/ox-beamer.el
> > +++ b/vendor/org-mode/lisp/ox-beamer.el
> > @@ -621,7 +623,7 @@ as a communication channel."
> >                                      (org-export-resolve-id-link link
> > info))))
> >                       ;; Now use user-defined label provided in TARGET
> >                       ;; headline, or fallback to standard one.
> > -                     (format "{%s}" (org-beamer--get-label target
> > info)))))))
> > +                     (format "%s" (org-beamer--get-label target
> info)))))))
> >         ;; Case 2: Creation of an appendix is requested.
> >         ((equal environment "appendix")
> >         (concat "\\appendix"
>
> Thanks for the debugging. Do you want to provide a patch against maint
> for this ? Note that your library needs to be updated.
>
> Regards,
>