Question on vacuum output

I am having some performance issues on some of my larger databases
(50-100+GB). I just ran a vacuum analyze on our key table, and saw this at
the end.

DETAIL: 562499 dead row versions cannot be removed yet.
There were 15117 unused item pointers.
0 pages are entirely empty.
CPU 8.32s/2.59u sec elapsed 340.19 sec.
INFO: analyzing "public.clmhdr"
INFO: "clmhdr": scanned 30000 of 221695 pages, containing 259684 live rows
and 75400 dead rows; 30000 rows in sample, 1919021 estimated total rows
VACUUM

What does this mean that there are 562499 dead row versions that could not
be removed? Could this be part of the performance issue? I have a query
that before the vacuum was running in 1-2 seconds and normally after a
vacuum analyze will run in a couple hundred miliseconds. (Although this run
of the vacuum analyze does not appear to have helped much, my tell tale
query is still running 1sec+).

Thanks,

Chris