swap stretching and running.

don't stretch before your workout, stretch after.

light running for 5-10 minutes is a decent general purpose warmup.

keep up the good work

identify some goals and post them up here, we will be able to help you plan a good method for accomplishing them

not bad

did you do heavy lifting before?

If you haven't then it looks like your primary goal should be body composition improvement -- getting your BF% (body fat %) down between 7 and 12% (assuming you are male)

if that is the case you may want to consider some metabolic conditioning and high intensity routines to start until you hit your body comp goals, then work on your strength. 

You can work on strength first, of course, but i tend to think that body comp is more important because its:
 1) more motivating for beginners
 2) easier to get started on your own.

Plus, having less BF makes it a lot easier to learn a lot of parkour skills and "moves".

If this is the case, let me know and we can recommend some bodyweight progression routines you can do to condition your metabolism and body comp

what are your specific goals?  just the APK WU in under 20?

If those are your only goals then this isn't too hard to accomodate...

Squats - Continue to do this as part of the APK WOD.  Make sure your form is SOLID totally on lock.  To increase your progress on squats for speed, tabata squats at least once every other week.

Pull-Ups - Depends on how many pullups you can do now.  Make sure they are full ROM and learn how to do kipping pullups.  I can give more specific recommendations if you let me know your current max - strict and kipping.

Pushups  - Same as pullups.  Make sure they are proper and full ROM.  Do these on rings or parallettes if you can to involve as many muscles as possible through a full ROM to optimize gains.

High Knees, one step per-block                  \
                                                             \
High Knees, two steps per-block                   \
                                                               /  See notes below
Side-step, two steps per-block                     /
                                                             /
High Knees, backwards, one step per-block  /
                                                           /
Butt-kicks, one step per-block                 /

If these 4 things are a problem for you then you need to just keep doing them.  This is mostly skill work.  If they have you totally winded, you may want to consider metabolically conditioning yourself to increase your endurance since this is pretty light work.

Burpee/Quadrapedal Movement- Perform 5-count burpees, one count for each movement, in control. After 3, perform :30-1:00 of random, varied quadrapedal movement. Repeat as needed or as you feel inspired to

Just keep working QM and Burpees.  The pushup and squat work will help your burpees.  Practice QM SLOWLY at first, make sure you get the hang of reciprocating joint movements.

If this is seriously your only set of goals it is a short matter of time before this list gets a whole lot bigger.

Consider some of the skills from www.beastskills.com/tutorials for ideas, or steve's workout routine thread:
http://www.americanparkour.com/smf/index.php?topic=9469.0

I have no problem with the agility work but the pullups, push ups, and squats keep me pretty winded.  Well, more specifically the pull-ups.  My pull up max, dead-hang w/ palms out is ~6, I work out with about 5 with the fifth of the third set barely being completed at my last workout.

How regularly should I do the APK warm up?  Daily?

EDIT  The reason I ask about the frequency is that my muscles are still a good bit sore from the previous time.  Should I just "man-up" and push through, or give myself more time to recover?

5:00 - run
15:00 - apk wu first half

3 sets of:
15 squats
~6 Kipping pullups (awful form I'm sure)
10 pushups
10 Samson streches

~5:00 rest

~5:00 light agility work

3 sets of:

30 high knees
20 butt kicks
3 5-count burpees

~10:00 mins of stretching to wrap it up

post your reps in each of the tabata sets, if you can.

keep a piece of paper and pen handy while you do them

tabata sets arent about "completion".  technically, u can do 1 per round and it be tabata.  What you need to do is do things as fast as you can.  I can get a tabata score with min reps of 21 if im feelin really good about it.  Get those squats and get them FAST!!:)

Aim for 20 rep minimum on the squats.  Thats a good first goal.

If you dont feel like thats a cardio workout afterwards, then you're doing it very wrong