I can't really tell in which cases this happens, but I have an example that does return wrong tick values reliably for me:

> plot(0:4)
> get(gca, 'ytick')
ans =

   0   1   2   3   4
> get(gca, 'xtick')
ans =

   1   2   3   4   5

There are ticks at 0.5, 1.5 etc. in the plot, so the expected and correct results would be:

> get(gca, 'ytick')
ans =

    0.00000    0.50000    1.00000    1.50000    2.00000    2.50000    3.00000    3.50000    4.00000
> get(gca, 'xtick')
ans =

    1.0000    1.5000    2.0000    2.5000    3.0000    3.5000    4.0000    4.5000    5.0000

Plotting 0:3 works fine and so does 0:5.
1:5 and 0:2:8 both have the same issue.

I'm running Octave 3.6.2 with Gnuplot 4.6 patchlevel 0 on Debian Wheezy. More specifically, I have these octave packages installed:
liboctave1 (3.6.2-5+deb7u1, amd64)
octave (3.6.2-5+deb7u1, amd64)
octave-common (3.6.2-5+deb7u1, all)
octave-htmldoc (3.6.2-5+deb7u1, all)
octave-info (3.6.2-5+deb7u1, all)
octave-io (1.0.19-1, amd64)
octave-java (1.2.8-6, amd64)
octave-miscellaneous (1.1.0-1, amd64)
octave-nan (2.5.5-2, amd64)
octave-octcdf (1.1.4-2, amd64)
octave-plot (1.1.0-2, all)
octave-statistics (1.1.3-1, all)
octave-strings (1.1.0-1, amd64)