A new algorithm is presented for rate-fidelity optimal packetization of scalable source bit streams with uneven erasure protection. It provides the globally optimal solution for input sources of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing n packets is monotonically decreasing in n, and independent erasure channels with packet erasure rate smaller than 0.5. The time and space complexities of the new algorithm are both O(NL), where N is the number of packets and L is the packet payload size, comparing to the O(NL2) time and space complexities of the existing globally optimal solution. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the globally optima.