dpkg warning regarding error in parsing file /var/lib/dpkg/available

My lsb_release -a

LSB Version: core-2.0-amd64:core-2.0-noarch:core-3.0-amd64:core-3.0-noarch:core-3.1-amd64:core-3.1-noarch:core-3.2-amd64:core-3.2-noarch:core-4.0-amd64:core-4.0-noarch:cxx-3.0-amd64:cxx-3.0-noarch:cxx-3.1-amd64:cxx-3.1-noarch:cxx-3.2-amd64:cxx-3.2-noarch:cxx-4.0-amd64:cxx-4.0-noarch:desktop-3.1-amd64:desktop-3.1-noarch:desktop-3.2-amd64:desktop-3.2-noarch:desktop-4.0-amd64:desktop-4.0-noarch:graphics-2.0-amd64:graphics-2.0-noarch:graphics-3.0-amd64:graphics-3.0-noarch:graphics-3.1-amd64:graphics-3.1-noarch:graphics-3.2-amd64:graphics-3.2-noarch:graphics-4.0-amd64:graphics-4.0-noarch:printing-3.2-amd64:printing-3.2-noarch:printing-4.0-amd64:printing-4.0-noarch:qt4-3.1-amd64:qt4-3.1-noarch
Distributor ID: Ubuntu
Description: Ubuntu 11.04
Release: 11.04
Codename: natty

Could you run command
   head -14993 /var/lib/dpkg/available | tail -20
and post result

 head -14993 /var/lib/dpkg/available | tail -20
Description: Basic TCP/IP networking system
 This package provides the necessary infrastructure for basic TCP/IP based
 networking.
Original-Maintainer: Marco d'Itri <email address hidden>

Package: libmagic1
Priority: standard
Section: libs
Installed-Size: 2044
Maintainer: Ubuntu Developers <email address hidden>
Architecture: amd64
Source: file
Version: 5.04-5ubuntu2
Depends: libc6 (>= 2.8), zlib1g (>= 1:1.1.4)
Suggests: file
Conflicts: file (<< 5.04-2)
Size: 204976
Description: File type determination library using "magic" numbers
 This library can be used to classify files according to magic number tests. It
 implements the core functionality of the file command.

Sorry, it seems file has changed since error was reported.

Try this instead

tail -n +14993 /var/lib/dpkg/available | head -20

I have the same problem with a different package, haven't quite resolved it yet.

Running "dpkg --clear-avail" solved it for me.