Is there an easy way to humanize midi notes without affecting velocity?

I believe there is a CAL script for it (not in front of the system right now). 
You can check this article out:
http://www.hexachord.net/cakewalk-cal/
 

IIRC there's a randomize function in the Quantize MIDI plug-in. 

My $.02: Most of the 'humanity' in a human performance is due to dynamics, duration, and, if not a keyboard instrument, attack and expression (volume change over the duration). Timing variation accounts for a lot less of what sounds 'human' than you might imagine. And random timing is not the same as 'grooving' or 'swinging' timing in any case.
 
I can quantize start times of one of my own keyboard performances to 100%, and it's still clearly a live performance and just sounds super-tight as opposed to robotic. And when timing is important to the feel, it's usually just that one or two notes in each measure are played significantly early/late/rubato, as opposed to all of them being randomly off the grid in either direction by small amounts.
 
Bottom line: If you have a sequence that doesn't sound natural, I would suggest you look at velocity and duration first (or again). And if the timing still sounds robotic, try varying the tempo a few BPM from measure to measure rather than randomizing the timing.

+1
Humanity is many things. Random it is not. 

I use the humanize plugin from Frank's Midi Plugins

This might strike some folks as rather 'barbaric/rudimentary' but once you try it you might take a different view:
Create a new track in your arrangement and record yourself 'tapping' along to the music using a short percussion instrument sound. Copy this 'tap' track to the clipboard and then apply Groove Quantise to your MIDI tracks with a resolution that matches the pulse of the tapping e.g. usually quarter notes or eighths (depending on the tempo and with a 0% Duration slider setting and conservative 'sensitivity' setting - if the OP doesn't want the velocity affected just reduce the Velocity slider to 0% also) This will allow your music to breathe in and out with a very natural human rubato (but won't mess up the timing of your shorter note length phrases.) Although most of the randomization offered by software does reduce the 'robotic' and stiff 'machine gun' effects we strive to avoid, for me, the results are inherently 'unmusical' as humans don't deviate from a fixed pulse in a random manner: they are deliberately ahead or behind the beat depending on how they perceive the feel of the groove. Time for my nap methinks....

+1 to brundlefly ( Dave) post 
 
If you create music with a machine it will sound like a  machine. So drawing notes has it's limitations.  
If you play the part with some talent (hopefully) involved it will sound human, even with tweaking afterwards. 
I've edited midi for over 30 years and lots of it was played by top notch Keyboard players. I agree that the start times are critical. Randomizing Quantization only makes it sound sloppy. So what Dave said is bang on with my experience too. 
And with drums there is certainly a narrow margin you can push a snare or tom hit. Kick stays locked. Hi Hat is all about articulation but never off the beat. 
 
Even though I'm not a drummer or a keyboard player, over time I have had to try and improve these skills as I find it is the only real answer to good sounding tracks. Otherwise I find real players to come in and play them when my attempts fail. We now have the option of sharing on the internet too. There are many music hobbyist out there to connect with for free. Cubase now has this built into their software. Bet ya Sonar will follow soon.  

Groove quantise. Does a good job, it humanizes to a groove rather than pure random sloppiness.

Another +1 to Brundlefly's post above.

Also bear in mind that a stereo image boils down to volume, pan, and EQ in its most basic form; so locking velocity specifically makes one component "static," which is not "human."