How to make a figure span two columns for Oxford Bioinformatics Journal template?

This minimal example will definitely work [now edited so that it also works with the latest bioinfo.cls]:

\documentclass{bioinfo}
\copyrightyear{2005}
\pubyear{2005}

\access{Advance Access Publication Date: Day Month Year}
\appnotes{Manuscript Category}

\begin{document}

\firstpage{1}

\subtitle{Subject Section}
\title[Long title]{Long and boring title} 
\author[Author et al.]{The authors}
\address{Research Institute}
\history{Received on XXXXX; revised on XXXXX; accepted on XXXXX} 
\editor{Associate Editor: XXXXXXX}
\corresp{To whom correspondence should be addressed.}
\abstract{The abstract.}

\maketitle

Science!

\begin{figure*}
  \includegraphics[width=\textwidth]{example-image-a}
  \caption{A caption.}
\end{figure*}

\end{document}

Also, I wouldn't recommend changing the bioinfo.cls file if you're intending to submit this to the journal, as their submission system will use the original class file for compiling your latex document.

So I can't seem to comment since my reputation isn't high enough, but I ran into the same problem and was able to solve it using FrankD's solution.

The problem is, figures seem to be pushed to the next page they appear in by the template. However, the template also forces pages to end when the text ends. So if the figure appears in the code on page 1, it wants to display it on page 2. But if the text ends at page 1 as FrankD's minimal example does, then page 2 is removed along with the figure. However, if you have enough text to make it to page 2, then the figure will show.

The following example will show the figure on page 2.

\documentclass{bioinfo}
\usepackage{lipsum} %Dummy text

\copyrightyear{2005}
\pubyear{2005}

\access{Advance Access Publication Date: Day Month Year}
\appnotes{Manuscript Category}

\begin{document}

\firstpage{1}

\subtitle{Subject Section}
\title[Long title]{Long and boring title} 
\author[Author et al.]{The authors}
\address{Research Institute}
\history{Received on XXXXX; revised on XXXXX; accepted on XXXXX} 
\editor{Associate Editor: XXXXXXX}
\corresp{To whom correspondence should be addressed.}
\abstract{The abstract.}

\maketitle

\lipsum[1-2] %Dummy text

\begin{figure*}
  \includegraphics[width=\textwidth]{workflow.png}
  \caption{ A caption.}
\end{figure*}

\lipsum[3-12] %Dummy text

\end{document}

If you put \lipsum[3-12] above \begin{figure*}, the figure will disappear (since it is being pushed to page 3).