>           (generate-new-buffer-name "foo")
>                => "foo<5>"
>           (generate-new-buffer-name "foo" "foo<3>")
>                => "foo<3>"
>           (generate-new-buffer-name "foo" "foo<6>")
>                => "foo<5>"
>
> However, for me all these forms evaluate to "foo"

This might be obvious, but: Do you actually have existing buffers named "foo", "foo<2>", "foo<3>", and "foo<4>" as described in the paragraph before that example code?