I used ModelBuilder and I did a field sort followed by calculate field using the sort code below and it worked great.  

Previously, I had tried these two steps outside of ModelBuilder and it failed.

Expression:

    autoIncrement()

Expression Type:
PYTHON_9.3

Code Block:

    rec=0
    def autoIncrement():
        global rec
        pStart = 1 #adjust start value, if req'd 
        pInterval = 1 #adjust interval value, if req'd
        if (rec == 0): 
            rec = pStart 
        else: 
            rec = rec + pInterval 
        return rec