My solution is here:
    http://www.dave.burt.id.au/ruby/barrel_of_monkeys.rb
It requires YAMLized song library, such as that available here:
    http://www.dave.burt.id.au/ruby/SongLibrary.zip
And it requires my solution to last week's quiz, HighLine::Dave, available 
here:
    http://www.dave.burt.id.au/ruby/highline/dave.rb

Get the lot here:
    http://www.dave.burt.id.au/ruby/barrel_of_monkeys.zip

The core of my solution is a function (BarrelOfMonkeys#playlist) that 
constructs playlists from the library matching criteria passed as parameters 
to the function, and also the requirement that all songs begin with the last 
letter of the previous song.
The criteria this function accepts include first letter, last letter, bounds 
and targets for number of songs and duration, and excluded songs.

When run as an application, my barrel_of_monkeys.rb prompts the user for 
these parameters, passes them to this function and returns the result.

A weakness in my solution, that I'd remove if I had time, is that the 
playlist-constructing search is depth-first, which means that a query "find 
the playlist with the least number of songs" takes the same time as "find 
the playlist with the most songs".

Now, for the quiz criteria:

1) My solution doesn't take starting and ending songs, it takes first and 
last letters. To find a playlist to join "Peace Train" and "Go Tell it on 
the Mountain", you would enter first letter => "n", last letter => "g".

Note that my solution ignores dangly bits on the end of a song's name, like 
"(Hardcore remix)" or "feat. Albert", when calculating a song's first and 
last letters. And a song has to have at least one actual alphabetic letter 
to really be considered.

2) You can enter a target duration. You can also set bounds on the duration, 
which allows a query like "as close as possible to 5 minutes, but no longer" 
(max duration => 300_000, target duration => 300_000)

3) Similarly to above, you can find the shortest playlist by setting the 
target duration or target songs to 0 or 1.

An example session is given below, and that's all. Thanks for another quiz.

Cheers,
Dave

Loading...done.
What letter should the first song start with? z
What letter should the last song end with? a
Minimum songs in playlist: [1]
Maximum songs in playlist (more than 3 could take a while): [5115] 3
Target number of songs: [no target] 1
Minimum duration in milliseconds: [0]
Maximum duration in milliseconds: [Infinity]
Target duration in milliseconds: [no target]
Generating playlists...done in 41.063 seconds.
Found 61 playlists:
<Playlist tracks: 2, duration: 0:9:20>
 1. Banco de Gaia - Zeus No Like Techno (6:01)
 2. Buena Vista Social Club - Orgullecida (3:19)
....
<Playlist tracks: 2, duration: 0:9:08>
 1. The Cranberries - Zombie (5:06)
 2. The Carpenters - Every Sha La La La (4:02)
Another barrel of monkeys? [yN] y
What letter should the first song start with? z
What letter should the last song end with? a
Minimum songs in playlist: [1] 3
Maximum songs in playlist (more than 3 could take a while): [5115] 3
Target number of songs: [no target]
Minimum duration in milliseconds: [0]
Maximum duration in milliseconds: [Infinity]
Target duration in milliseconds: [no target] 999999999
Generating playlists...done in 47.656 seconds.
Found 1 playlist:
<Playlist tracks: 3, duration: 7:44:06>
 1. Cherry Poppin Daddies - Zoot Suit Riot (3:53)
 2. Robert A. Heinlein - The Menace from Earth (452:54)
 3. Afro Celt Sound System - Hypnotica (7:18)
Another barrel of monkeys? [yN]