############## BASH ###############

#!/bin/bash
set -u

function mins_between {
    echo $((( `date +%s -d "$1"` - `date +%s -d "$2"` ) / 60 )) | sed 's/-//'
}

This has the overhead of recognizing the input format, but it's bash so efficiency discussion isn't that important here. It's elegant, it's readable and we aren't reinventing any wheels, which is what we should aim for with bash.

############## JAVA ################

public long minsBetween(String date1, String date2) throws ParseException {
    SimpleDateFormat parser = new SimpleDateFormat("EEE, d MMM yyyy HH:mm:ss Z");
    return Math.abs(parser.parse(date1).getTime() - parser.parse(date2).getTime()) / 60000;
}

Again, not trying to reinvent any wheels here - usually when you try to reinvent the wheel you don't end up with a better wheel.  Nevertheless if you wanted the "worlds fastest RCF 2822 mins between dates calculator" I'd use C and clever tricks to get the machine instructions down to the absolute minimum.  Like using the fact that a month is uniquely determined by the sum of the ascii values of the second two characters, and we can compute absolute value using bit operators, and pre-compiling a 2D array which holds the Gregorian Calendar (would need to be about 2 MB in size) giving us a <month, year> lookup on mins rather than computing on the fly, and don't use atoi, etc, etc, etc.  I can't see a reason why you'd need a really really fast dateBetween function, so the exercise would be purely for fun (and good fun at that!)