Can you post the output of
sudo apt-get install libavcodec51

or 
sudo apt-get install libavcodec-unstripped-51  ?

Thanks!

Sure thing, here you go:

[skip uneventful output from `sudo apt-get update`]

vanessa@rainbird:~$ sudo apt-get install libavcodec51
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  libkexiv2-3-kde3
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  libavformat52
The following NEW packages will be installed:
  libavcodec51
0 upgraded, 1 newly installed, 1 to remove and 39 not upgraded.
Need to get 0B/1132B of archives.
After this operation, 1532kB disk space will be freed.
Do you want to continue [Y/n]? n
Abort.
vanessa@rainbird:~$

On another machine in our house (my husband's), this same error is occurring.  While his system doesn't have MythTV, it does have other utilities which depend on libavcodec52 (such as vlc, the ffmpeg plugin for sox, and a few other things).

Just giving this bump asI can't burn audio CD's with k3b until this bug is fixed.

(In reply to comment #4)
> Just giving this bump asI can't burn audio CD's with k3b until this bug is
> fixed.

Sorry for the delay; I just completed a really hectic project at work... 

For now, you can install libavcodec-unstripped-51 instead of libavcodec51 with no problems.  I'm still trying to figure out why libavcodec51 is broken.

It looks like this will have to wait until k3b is ported to the new ffmpeg:
libavformat52: Breaks: libavcodec51 but 4.0~0ubuntu0 is to be installed.

I have no control over the libavformat52 package.

This doesn't work here.

vanessa@rainbird:~$ sudo apt-get install libavcodec-unstripped-51
[sudo] password for vanessa:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
  libavcodec-unstripped-52 libavutil-unstripped-49 libx264-65
The following packages will be REMOVED:
  libavcodec52 libavutil49
The following NEW packages will be installed:
  libavcodec-unstripped-51 libavcodec-unstripped-52 libavutil-unstripped-49
  libx264-65
0 upgraded, 4 newly installed, 2 to remove and 0 not upgraded.
Need to get 4286kB of archives.
After this operation, 811kB of additional disk space will be used.
Do you want to continue [Y/n]?
Get:1 http://ppa.launchpad.net jaunty/main libavcodec-unstripped-51 4.0~0ubuntu0 [1154B]
Get:2 http://us.archive.ubuntu.com jaunty/multiverse libavutil-unstripped-49 3:0.svn20090303-1ubuntu2+unstripped1 [93.5kB]
Get:3 http://us.archive.ubuntu.com jaunty/multiverse libx264-65 1:0.svn20081230-0.0ubuntu1 [298kB]
Get:4 http://us.archive.ubuntu.com jaunty/multiverse libavcodec-unstripped-52 3:0.svn20090303-1ubuntu2+unstripped1 [3893kB]
Fetched 4286kB in 15s (268kB/s)
dpkg: libavutil49: dependency problems, but removing anyway as you request:
 libpostproc51 depends on libavutil49 (>= 3:0.svn20090303) | libavutil-unstripped-49 (>= 3:0.svn20090303); however:
  Package libavutil49 is to be removed.
  Package libavutil-unstripped-49 is not installed.

That dpkg warning repeats quite a few times, over and over.  Among the repeats is the usual output from dpkg and apt-get, ending with:

(Reading database ... 150393 files and directories currently installed.)
Unpacking libavutil-unstripped-49 (from .../libavutil-unstripped-49_3%3a0.svn20090303-1ubuntu2+unstripped1_i386.deb) ...
Selecting previously deselected package libx264-65.
Unpacking libx264-65 (from .../libx264-65_1%3a0.svn20081230-0.0ubuntu1_i386.deb) ...
Selecting previously deselected package libavcodec-unstripped-52.
Unpacking libavcodec-unstripped-52 (from .../libavcodec-unstripped-52_3%3a0.svn20090303-1ubuntu2+unstripped1_i386.deb) ...
Selecting previously deselected package libavcodec-unstripped-51.
Unpacking libavcodec-unstripped-51 (from .../libavcodec-unstripped-51_4.0~0ubuntu0_all.deb) ...
Setting up libavutil-unstripped-49 (3:0.svn20090303-1ubuntu2+unstripped1) ...

Setting up libx264-65 (1:0.svn20081230-0.0ubuntu1) ...

Setting up libavcodec-unstripped-52 (3:0.svn20090303-1ubuntu2+unstripped1) ...

Setting up libavcodec-unstripped-51 (4.0~0ubuntu0) ...
Processing triggers for libc6 ...
ldconfig deferred processing now taking place


That looked like it went in OK, despite the warnings, so I next tried to install the libk3b3... package, but it fails the same as before:

vanessa@rainbird:~$ sudo apt-get install libk3b3-extracodecs-kde3
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
  libk3b3-extracodecs-kde3: Depends: libavcodec51 (>= 3:0.svn20080206-8) but it is not going to be installed or
                                     libavcodec-unstripped-51 (>= 3:0.svn20080206-8) but 4.0~0ubuntu0 is to be installed
E: Broken packages
vanessa@rainbird:~$

I have finally succeeded at building K3B properly under Jaunty, so this bug should now be fixed.  Can you please verify this?

Thanks!

Sure enough.  The problem seems to be solved.  I did an update and dist-upgrade, then brought in the missing package.  K3B seems to be quite happy now to add MP3s to an audio CD.  I think you can safely close this report and mark it as "fixed".

Glad it's finally fixed--thanks for reporting!