You are correct that celerrimus can and should be translated as a noun. Allen & Greenough has a section dedicated to Adjectives used substantively.
You don't make it explicit in your question, but it is possible that the real source of confusion is that celerrimus has two expected characteristics:
- It is nominative, although the surrounding structure is accusative + infinnitive.
- It is masculine, although navis is feminine.
The "expected" construction would read:
Phasellus...ait [se] fuisse navium celerrimam.
The vessel said that she was the fastest of ships.
It's worth noting that this expected accusative occurs in the next phrase!
[Phasellus ait] ... ullius natantis impetum trabis nequisse praeterire.
[The vessel said] that the advance of any other floating plank could not pass it by.
The first possible explanation, that this is a transcription error, is given in the other answer. I am not familiar with the manuscript tradition, so I cannot speculate on how likely this is.
Another explanation is that this is an imitation of a Greek construction: attraction in case (and, in this case, gender as well).
This is what Merrill has to say about this passage, along with two examples from Horace:
celerrimus: an instance of so-called attraction in case, more common in Greek than in Latin, but not so rare in the Augustan age (especially in Ovid) and later; cf. Hor. Ep. 1.7.22 “vir bonus et sapiens dignis ait esse paratus.” The adjective here is also attracted from the gender of navium into that of phasellus; cf. Hor. S. 1.9.4 “dulcissime rerum.”
Regarding your translation attempt, you seem to have most of the vocabulary (though you skip impetum and opus and mistake volare [fly] for velle [want]), but I have a general piece of advice: Try to step back and view the sentence as a whole before translating individual components.
Catullus is writing poetry and likes to mix words together for pleasing effect, but this means that a "word by word" translation without an eye to the overarching idea is inevitably going to fail. The "litmus test" at the end of a translation should first be: does this make any sense? (As far as I know, Romans didn't compose post-modernist poetry :)
Here are three things that I would try to notice in this passage:
- ullius natantis impetum trabis: every word except impetum is in the genitive, so we know that we should put them together and it is likely that they modify impetum.
- sive palmulis...sive linteo: sive is used in parallel constructions: in this case, it is followed by an ablative. This means it is likely that these two ablatives are serving the same purpose, i.e. means: "either by oars or by linen (=sail)."
- opus foret: This is an idiomatic construction. You can find in a dictionary that opus est + infinitive means "it is necessary to X."
Good luck with the rest of Catullus!