I have been running a non-exit tor relay for a few months now. It's on a metered VPS, so after some experimenting I found that I can afford about this much bandwidth:

  RelayBandwidthRate 250 KB  
  RelayBandwidthBurst 500 KB 

This worked fine until recently. However, just today I noticed the machine was sluggish, and sure enough tor was using 99% cpu and dumping these messages to syslog:

Your computer is too slow to handle this many circuit creation requests! Please consider using the MaxAdvertisedBandwidth config option or choosing a more restricted exit policy. [2022 similar message(s) suppressed in last 60 seconds]

Digging deeper, I've seen these messages pop up from time to time over the last 30 days or so, but not consistently, and I've never noticed the cpu pegged (but it could have happened, I don't use the machine that often).

I tried including:

  MaxAdvertisedBandwidth 50 KB

and 

  # https://lists.torproject.org/pipermail/tor-relays/2012-May/001352.html
  MaxOnionsPending 250

to no avail. I have had to dial all the way down to:

  RelayBandwidthRate 40 KB
  RelayBandwidthBurst 80 KB

and that seems to make the messages go away, but the cpu is still pegged and the machine is sluggish. 

It's running on an up-to-date debian squeeze (6.0.7), with tor 0.2.3.25-1~~squeeze+1 and openssl 0.9.8o-4squeeze14.

I run updates fairly often. I upgraded to this version of tor a couple of weeks ago, which could be related, but doesn't correlate perfectly to when I first find the "too slow" messages in my logs. The only other recent updates that seem plausibly related are libbind/libisc/libisccc/etc.