[Post edited for clarity and simplicity.]
This issue has been bothering me for a few months now, though I've only recently figured out what it is and what causes it.
A few months ago, there were updates to GStreamer in Debian SID/Unstable that caused Banshee to occasionally stall at the beginning of a new track, though at the time I couldn't figure out why, or the responsible package(s), so I just held back the entire group and thought nothing of it. Those updates eventually made there way into Testing, though I kept them held back since the issue still had not been fixed.
When the RC for LMDE's new ISO was available, I downloaded it, checked that the GStreamer versions were the newer ones, and tested the RC out, making note of whether or not the issue occurred. At the time it did not, so I resolved to install both the newer LMDE respin and Mint 13 when they were officially released, believing that the issue was somehow related to something on my current installs and would go away if I installed the new versions (with the newer GStreamer packages) fresh.
I recently did install both OSes fresh, and while I was using them as I normally do, I discovered that the issue did not go away as I thought it would. I then realized that perhaps the issue did not appear during the testing of the RC because I had not being playing music the same way I normally do (entire library on Shuffle), but had been playing entire albums straight through. I began playing albums straight through the same way I had when testing the RC, and for a while the issue did not occur, however when I began playing through an album which contained mostly FLAC files with a handful of MP3s scattered throughout, the issue began occurring again. I did not realize the connection immediately, however once I did, I loaded up the play queue with a mixture of MP3s and FLAC files from a handful of albums, manually sorting it to be aware of both format changes and album changes, then began playing through it. Sure enough, Banshee's playback would stall at the beginning of a new track if the previous track was an MP3 and the new track was a FLAC file, and occasionally it stalled between two FLAC files from different albums.
Once I determined this, and verified that it was consitently reproducible, I set out to find the package(s) responsible. It turns out that libgstreamer-plugins-base0.10-0 version 0.10.36-1 causes this issue, reverting it (and its dependants) to an earlier version removes the issue in both LMDE and Mint 13.
I would like others to do some similar testing, if it's not too much trouble, possibly using other file formats or other media players that ustilize GStreamer, to verify if this issue occurs for them, and possibly if it affects track changes between other formats than MP3 to FLAC, or other media players. Some possible steps to follow are outlined below:
1) Load up the media player's queue with tracks of various formats, manually sorting the queue to be aware of when a format change will occur, and which formats it's switching from and to.
2) When a format switch will occur, make note of the format of the previous track and the format of the new track, and whether or not playback stalled at the beginning of the new track.
3) Please post any findings here: which media player was used, which formats were tested and whether or not playback stalled when switching from one format to another
I plan to file a bug report with both Debian and Ubuntu about this, and it would be helpful to know everything possible about this issue, which media players it affects as well as which formats cause it to stall when switching from which other formats.