Reformat/reflow to your liking. Preferably with Perl::Tidy, so the new layout is both documented and reproducible.
Do not rewrite function-based code to OO-based code just because it is more modern. There may be (very) good reasons other than modernizing the code, but simply because you think OO is more modern or because you like OO is a very bad reason for such a conversion. To me that sounds like implementing threads in a program that doesn't gain anything by that.
Add comments! Everywhere that you needed time to investigate, add comments.
Start writing tests based on the docs and based on any fix you make.
Replace local option parsing functions with Getopt::Long and write a good usage function.
Create a two-sided TODO list. On the left "Have to change", on the right "would love to change". Postpone the right until everything works and you have spare time.
Use a good VCS, like git and commit often with very clear commit messages.
Snippets of code should be wrapped in
<code> tags not<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
