Readelf's output shows that the symbol is present, so this may be something else (broken/old copy in /usr/local/lib perhaps?):
$ readelf -Ws ubuntu/usr/lib/libavcodec.so.53.6.0 |grep avcodec_init 1395: 003ca330 31 FUNC GLOBAL DEFAULT 12 avcodec_init@@LIBAVCODEC_53
$ readelf -Ws medibuntu/usr/lib/libavcodec.so.53.6.0 |grep avcodec_init 1476: 003cfeb0 31 FUNC GLOBAL DEFAULT 12 avcodec_init@@LIBAVCODEC_53
$ readelf -Ws ubuntu/usr/lib/i686/cmov/libavcodec.so.53.6.0 |grep avcodec_init 1395: 003ca7b0 31 FUNC GLOBAL DEFAULT 12 avcodec_init@@LIBAVCODEC_53
$ readelf -Ws medibuntu/usr/lib/i686/cmov/libavcodec.so.53.6.0 |grep avcodec_init 1476: 003d0330 31 FUNC GLOBAL DEFAULT 12 avcodec_init@@LIBAVCODEC_53
Readelf's output shows that the symbol is present, so this may be something else (broken/old copy in /usr/local/lib perhaps?):
$ readelf -Ws ubuntu/ usr/lib/ libavcodec. so.53.6. 0 |grep avcodec_init init@@LIBAVCODE C_53
1395: 003ca330 31 FUNC GLOBAL DEFAULT 12 avcodec_
$ readelf -Ws medibuntu/ usr/lib/ libavcodec. so.53.6. 0 |grep avcodec_init init@@LIBAVCODE C_53
1476: 003cfeb0 31 FUNC GLOBAL DEFAULT 12 avcodec_
$ readelf -Ws ubuntu/ usr/lib/ i686/cmov/ libavcodec. so.53.6. 0 |grep avcodec_init init@@LIBAVCODE C_53
1395: 003ca7b0 31 FUNC GLOBAL DEFAULT 12 avcodec_
$ readelf -Ws medibuntu/ usr/lib/ i686/cmov/ libavcodec. so.53.6. 0 |grep avcodec_init init@@LIBAVCODE C_53
1476: 003d0330 31 FUNC GLOBAL DEFAULT 12 avcodec_