I couldn't reliably pin it down, but the bug seems to be rather frequent with me. Some time after I first launch rekonq (a couple of hours or days - I tend not to close rekonq between sessions and my computer is always on), select keyboard shortcuts stop working.
To start with, "Ctrl+T" won't open a new tab and complains about the conflict of keyboard shortcuts (although there are none). Relaunching rekonq temporarily solves it. As I said, I cannot reliably reproduce it, but I suspect that this usually happens when I open more than one instance or window of rekonq, with more than one tab. In addition, the message about keyboard shortcuts appears on a different desktop (I have 4), so I usually cannot see the dialog window, and rekonq window becomes "unfocused". The same happens with "Ctrl+H" and several other shortcuts, although occasionally "Ctrl+T" works while "Ctrl+H" doesn't. And vice-versa.

Also, "Ctrl+Shift+B" (Bookmarks Panel) doesn't work at all. It complains that this combination is assigned to another shortcut (and points to a non-existant "Configure Shortcuts" in a non-existant "Settings" menu, btw). But even after digging through all available KDE shortcuts, I couldn't find another "Ctrl+Shift+B".

Reproducible: Sometimes

Steps to Reproduce:
1. Launch rekonq.
2. Browse random internet pages, opening a few tabs.
3. Launch another instance of rekonq, repeat (2).
3a. Optionally, try launching another instance of rekonq in another KDE workspace/activity.
4. Certain keyboard shortcuts stop working (occasionally).
Actual Results:  
Certain keyboard shortcuts (Ctrl+T, Ctrl+H, others) stopped working.

Expected Results:  
Keyboard shortcuts should always work.

(K)ubuntu 13.10, 64 bit.
KDE 4.11.3 (but I've been experiencing this bug since long ago).