-- UPDATE --
Damnit, latest Ubuntu has the same damn problem (Rhythmbox 0.13.3), 404 on the request. Example after 0.12.5 example.
-- END UPDATE --
Ye Olde Rhythmbox 0.12.5 is trying to use an old script on musicbrainz.org that doesn't exist anymore. The following is a capture of the failing request to obtain the album information.
POST /cgi%2dbin/mq%5f2%5f1.pl HTTP/1.0
Host: mm.musicbrainz.org
Accept: */*
User-Agent: libmusicbrainz/2.1.5
Content-type: text/plain
Content-length: 2484
<?xml version="1.0"?>
<rdf:RDF xmlns:rdf = "http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc = "http://purl.org/dc/elements/1.1/"
xmlns:mq = "http://musicbrainz.org/mm/mq-1.1#"
xmlns:mm = "http://musicbrainz.org/mm/mm-2.1#">
<mq:GetCDInfo>
<mq:depth>2</mq:depth>
<mm:cdindexid>q85Jz8YHGZs3pra.5mD0bQAqtWo-</mm:cdindexid>
<mm:firstTrack>1</mm:firstTrack>
<mm:lastTrack>10</mm:lastTrack>
<mm:toc>
<rdf:Seq>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>183530</mm:sectorOffset>
<mm:numSectors>0</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>150</mm:sectorOffset>
<mm:numSectors>22299</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>22449</mm:sectorOffset>
<mm:numSectors>16842</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>39291</mm:sectorOffset>
<mm:numSectors>17599</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>56890</mm:sectorOffset>
<mm:numSectors>15427</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>72317</mm:sectorOffset>
<mm:numSectors>16560</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>88877</mm:sectorOffset>
<mm:numSectors>17856</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>106733</mm:sectorOffset>
<mm:numSectors>20088</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>126821</mm:sectorOffset>
<mm:numSectors>28970</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>155791</mm:sectorOffset>
<mm:numSectors>15128</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>170919</mm:sectorOffset>
<mm:numSectors>12611</mm:numSectors>
</mm:TocInfo>
</rdf:li>
</rdf:Seq>
</mm:toc>
</mq:GetCDInfo>
</rdf:RDF>
HTTP/1.1 404
Date: Mon, 15 Aug 2011 04:31:09 GMT
Content-Type: text/html; charset=utf-8
Connection: close
Server: nginx/0.7.65
Content-Length: 10108
Set-Cookie: musicbrainz_server_session=whatever; path=/; expires=Mon, 15-Aug-2011 06:31:09 GMT; HttpOnly
Set-Cookie: javascript=false; path=/
And here's the latest Natty one (Rhythmbox 0.13.3):
POST /cgi%2dbin/mq%5f2%5f1.pl HTTP/1.0
Host: mm.musicbrainz.org
Accept: */*
User-Agent: libmusicbrainz/2.1.5
Content-type: text/plain
Content-length: 2484
<?xml version="1.0"?>
<rdf:RDF xmlns:rdf = "http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc = "http://purl.org/dc/elements/1.1/"
xmlns:mq = "http://musicbrainz.org/mm/mq-1.1#"
xmlns:mm = "http://musicbrainz.org/mm/mm-2.1#">
<mq:GetCDInfo>
<mq:depth>2</mq:depth>
<mm:cdindexid>q85Jz8YHGZs3pra.5mD0bQAqtWo-</mm:cdindexid>
<mm:firstTrack>1</mm:firstTrack>
<mm:lastTrack>10</mm:lastTrack>
<mm:toc>
<rdf:Seq>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>183530</mm:sectorOffset>
<mm:numSectors>0</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>150</mm:sectorOffset>
<mm:numSectors>22299</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>22449</mm:sectorOffset>
<mm:numSectors>16842</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>39291</mm:sectorOffset>
<mm:numSectors>17599</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>56890</mm:sectorOffset>
<mm:numSectors>15427</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>72317</mm:sectorOffset>
<mm:numSectors>16560</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>88877</mm:sectorOffset>
<mm:numSectors>17856</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>106733</mm:sectorOffset>
<mm:numSectors>20088</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>126821</mm:sectorOffset>
<mm:numSectors>28970</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>155791</mm:sectorOffset>
<mm:numSectors>15128</mm:numSectors>
</mm:TocInfo>
</rdf:li>
<rdf:li>
<mm:TocInfo>
<mm:sectorOffset>170919</mm:sectorOffset>
<mm:numSectors>12611</mm:numSectors>
</mm:TocInfo>
</rdf:li>
</rdf:Seq>
</mm:toc>
</mq:GetCDInfo>
</rdf:RDF>
HTTP/1.1 404
Date: Mon, 15 Aug 2011 14:40:53 GMT
Content-Type: text/html; charset=utf-8
Connection: close
Server: nginx/0.7.65
Content-Length: 10108
Set-Cookie: musicbrainz_server_session=removed; path=/; expires=Mon, 15-Aug-2011 16:40:53 GMT; HttpOnly
Set-Cookie: javascript=false; path=/