\begin{figure}[h]
As a last resort, you can get the 'float' package, and go
\usepackage{float}
...
\begin{figure}[H]
where the capital H means 'forget about your algorithm, I want it
'HERE'. This will always work as you want it. The downside is that
you may end up with a lot of whitespace on the page, which might
look odd. Another danger is that the figure might end up before
you refer to it in the text. Latex's algorithm ensures this never
happens, but if you over-ride it with H, that's what you get.
Basically, all these problems stem from the use of double-spaced text, which means there are sometimes no paragraph breaks on a page (and the para breaks are part of the algorithm to try to guess the best location for floats).