FFT seems more accurate than MUSIC algorithm?
I created a signal with two sinusoids and added increasing amounts of random noise to it. The results of running the FFT and MUSIC on this signal are shown in the image below.

You are using pmusic(). MUSIC (MUltiple SIgnal Classification) is a general algorithm that can estimate all kinds of parameters out of a signal. pmusic() is a MATLAB function that utilizes this algorithm to evaluate the locations of peaks' location in the spectrum of the signal. More to the point, it does not mind a better representation of the level in other frequencies (not the location of the peaks).

I thought the whole point of the MUSIC algorithm is that it is supposed to give more accurate results than the FFT.

Not at all! FFT is an analytical method to represent a given signal in the frequency domain. There can be a vast discussion on the accuracy of the method given the parameters it is executed with but it is a mathematical operation with a close solution. MUSIC algorithm, however, is an optimization method. As an optimization method, it is iteratively estimating the optimal solution to a problem. It can actually generate two different solutions given the same problem and two different initialization. Optimization methods are usually used when a close solution cannot be formulated. Each of these two can be better depending on the specifics of the problem. For example, how close are the frequencies? How fast to you want your solution? What is your tolerance for accuracy?