Validate parameters within a range

First off, I would like to point you to the time module which has functions that are similar to what you want to accomplish.

Now as for DRYing your code up a bit. You were right to notice that you have blocks of:

if var in range1:
    func1(var)
elif var in range2:
    func2(var)
else:
    return 'blah_out_of_range'

I don't agree with your else block code. You are returning an error statement, which should actually be an exception such as a ValueError like so:

raise ValueError("blah out of range")

This is more readable, and more Pythonic.

Back to the code block, if we take each of the variant parts as arguments into a super function we get:

def process(var, cond1, func1, cond2, final):
    # ugly code here

This is trying to emulate the functional programming style of Lisp, Scheme, Racket and etc, which something that is generally avoided in Python code due to the final unreadability of the code.

Let's think of something else, such as checking all the conditions ahead of time, before doing any processing. This speeds up execution for failed inputs (as any failing input would fail as fast as possible), and simplifies the logic.

This would look something like this:

if year not in range(1001, 2035):
    raise ValueError("year not in range")
if month not in range(1, 13):
    raise ValueError("month not in range")

and so on. This can also be done via assert statements of the unittest module for even more compact code.

Then afterwards you will have blocks of the form:

if cond1:
    func1
else:
    func2

This is easily wrapped into a ternary operator:

func1 if cond1 else func2

Which will eliminate a lot of lines from your code.

Python supports C-style string formatting:

mm = "%02d" % month

achieves your goal in just one line.

Thanks to answers from @vnp and @mleyfman, here is my suggestion. Down to 50 lines (formerly 95). While reviewing python string formatting, I found the String.zfill function, which appears to accomplish the same thing. This made it practical to support years of 1 to 4 digits, so functionality is expanded and docstring updated.

Timezone checking can be simplified with one basic range check. positive and small flags replaced with a more clear ternary switch to check for positive/negative sign while formatting, combined with zfill.

def rfc_3339_str(minutes = 0, secs = 0, year = 1999, month = 1, date = 1, time_zone = 0):
    '''Takes minutes and builds RFC 3339 timeDate string.  
        yyyy-mm-ddTHH:MM:ss[.mmm][+/-HH:MM].  Does not support milliseconds.  
        All params optional.  Timezone format is number in range 
        [-12:12] (hours only).  All numbers expect integers.
        Minutes > 1439 (23 hours 59 minutes) wrap around to zero,.
        Date defaults to 1/1/1999.  Supported years 1 CE - 2035 CE.  Date allows 
        range 0-31 inclusive for all months.  Negative times are not supported.  
        Incorrect params not guaranteed to cause errors (eg 5 digit years).'''
    plus = '+'
    date_time_split = 'T'
    date_split = '-'
    time_split = ':'
    time_zone_mins = ':00'
    MAX_MINUTES = 1440

    #validate inputs
    if year not in range(0, 2036):
        raise ValueError('year out of range')
    if month not in range(1,13):
        raise ValueError('month out of range')
    if date not in range(1, 32):
        raise ValueError('date out of range')
    if minutes < 0:
        raise ValueError('minutes out of range')
    while minutes > MAX_MINUTES:
        minutes = minutes - MAX_MINUTES
    hours_int = int(minutes / 60)
    mins_int = int(minutes % 60)
    if hours_int not in range(0,24):
        raise ValueError('hours out of range')
    if mins_int not in range(0,60):
        raise ValueError('minutes out of range')
    if secs not in range(0, 60):
        raise ValueError('seconds out of range')
    if time_zone not in range(-12, 13):
        raise ValueError('time zone out of range')

    #validation complete, format strings
    yyyy = str(year).zfill(4)
    mm = str(month).zfill(2)
    dd = str(date).zfill(2)
    HH = str(hours_int).zfill(2)
    MM = str(mins_int).zfill(2)
    ss = str(secs).zfill(2)
    zz = plus + str(time_zone).zfill(2) if time_zone in range(0,13) else str(time_zone).zfill(3)

    print(yyyy + date_split + mm + date_split + dd + 
        date_time_split + HH + time_split + 
        MM + time_split + ss + 
        zz + time_zone_mins)