Run the following and check if you still see the same problem:
plot(1:3,1:3,'ko-', 1:3,2:4,'ro-', 1:3,3:5,'bo-');
If you see the same problem it could mean that your legend function is corrupted. Run whos('legend','-all') and check if you have an unexpected version of the legend function on your Matlab path.
If you don't see the same problem, it might be a problem with your data in some strange way. In any case it will help narrow down the possibilities.