strange behaviour in keyboard macro

["Héctor Lahoz" <hectorlahoz@gmail.com>]

I saved a keyboard macro like this:

<<search-forward>>	;; search-forward
Priority:		;; self-insert-command * 9
SPC			;; self-insert-command
required		;; self-insert-command * 8
RET			;; newline
<<backward-paragraph>>	;; backward-paragraph
C-n			;; next-line
<<search-forward>>	;; search-forward
:			;; self-insert-command
SPC			;; self-insert-command
RET			;; newline

When I execute it sometimes it does what I mean and the cursor ends on the right line.
But sometimes it ends (erroneously) on the following line. For example (I added numbers
for reference):

1: Package: mypkg
2: xxxxxxxxxxxxxx
3:  xxxxxxxxxxxxxx
4: Priority: normal
5: 
6: Package: mypkg2
7: xxxxxxxxxxxxxx
8: Priority: required

backward-paragraph should set the cursor at line 5 (blank line) so
cursor should end up at line 6.

At first it seemed random. Then I tried to find a pattern and found
out that it has something to do with text scrolling. When I repeat the
macro starting at a distant point (like half the window size) I manage
to get alternating results, that is, with one execution it ends at
line 6 and with the next execution (reseting the start position) it
ends at line 7.

Emacs version 24.4.1. Fundamental mode.
Is this a bug? I think with emacs 23 it worked fine.