Yes! Usually it's not a problem, but every now and then relativenumber really kills performance.
The last time I noticed this was with valgrind logs; and I have no idea what exactly is causing it (amount of lines doesn't seem to be it).
Thankfully it's perfectly usuable for day-to-day editing. Binding :set rn! to a key circumvents this problem well enough.
I see considerable slowdown when using just vim on OSX. It could be a fault of something else, but I also find my 'b'ack word slowed down considerably as well.
Not sure what cursorline is, but relativenumber redraws pretty slowly when scrolling a lot (like jjjjjjjjj) in gVim on a pretty powerful Windows 7 machine. Haven't noticed anything on my linux netbook, but it runs a newer vim version.
Does anyone else have the same experience and perhaps a solution?