Just noticed this, while looking at the code, so I tried it out against
the record target (x86) on the reverse-20080930-branch branch.

4       int main ()
5       {
6               asm ("nop");
7               asm ("nop");
8               asm ("nop");
9               asm ("nop");
10      }

(gdb) disassemble
Dump of assembler code for function main:
0x08048344 <main+0>:    lea    0x4(%esp),%ecx
0x08048348 <main+4>:    and    $0xfffffff0,%esp
0x0804834b <main+7>:    pushl  -0x4(%ecx)
0x0804834e <main+10>:   push   %ebp
0x0804834f <main+11>:   mov    %esp,%ebp
0x08048351 <main+13>:   push   %ecx
0x08048352 <main+14>:   nop
0x08048353 <main+15>:   nop
0x08048354 <main+16>:   nop
0x08048355 <main+17>:   nop
0x08048356 <main+18>:   pop    %ecx

Now let's try reverse continuing until hitting a breakpoint at 0x8048353 (line 7):

  (gdb) b 7
  Breakpoint 1 at 0x8048353: file nop.c, line 7.
  (gdb) start
  Temporary breakpoint 2 at 0x8048352: file nop.c, line 6.
  Starting program: /home/pedro/gdb/reverse-20080930-branch/build32/gdb/nop

  Temporary breakpoint 2, main () at nop.c:6
  6               asm ("nop");
  (gdb) record
  (gdb) n

  Breakpoint 1, main () at nop.c:7
  7               asm ("nop");
  (gdb) n
  8               asm ("nop");
  (gdb) n
  9               asm ("nop");
  (gdb) p $pc
  $1 = (void (*)()) 0x8048355 <main+17>
  (gdb) reverse-continue
  Continuing.

  Breakpoint 1, main () at nop.c:7
  7               asm ("nop");
  (gdb) p $pc
  $1 = (void (*)()) 0x8048353 <main+15>
  (gdb)                             

Now, let's try reverse continuing to a breakpoint at 0x8048353 (line 6),
but this time, let's also sneak a breakpoint at 0x8048352 (line 6):

  (gdb) start
  Temporary breakpoint 1 at 0x8048352: file nop.c, line 6.
  Starting program: /home/pedro/gdb/reverse-20080930-branch/build32/gdb/nop

  Temporary breakpoint 1, main () at nop.c:6
  6               asm ("nop");
  (gdb) b 6
  Breakpoint 2 at 0x8048352: file nop.c, line 6.
  (gdb) b 7
  Breakpoint 3 at 0x8048353: file nop.c, line 7.
  (gdb) record
  (gdb) n

  Breakpoint 3, main () at nop.c:7
  7               asm ("nop");
  (gdb) n
  8               asm ("nop");
  (gdb) n
  9               asm ("nop");
  (gdb) p $pc
  $1 = (void (*)()) 0x8048355 <main+17>
  (gdb) reverse-continue
  Continuing.

  Breakpoint 2, main () at nop.c:6
  6               asm ("nop");
  (gdb) p $pc
  $1 = (void (*)()) 0x8048352 <main+14>

Oh-oh.  Not good.

So, in the second example, reverse execution should continue until
breakpoint 3, but, adjust_pc_after_break finds a breakpoint
at `PC - decr_pc_after_break' (1 on x86), adjusts the PC, and then we
report breakpoint 2 being hit.  The first example didn't trip on the
problem, because there was no breakpoint at `PC - 1' when GDB went to
look if adjustment was needed.

I'm guessing the attached patch should be correct for all
targets/archs, or could it be your targets are behaving differently?

-- 
Pedro Alves