Ahh, this is just a simple bug in the command-not-found package that makes those recommendations when you type in a missing binary, not an underlying problem with the entire philosophy of splitting pacakges!
I'm not sure it's really a bug with command-not-found: I think in this case it correctly gives the package containing the erl command, namely erlang-base; the problem is that Ubuntu decided that there should exist an erlang-base package that gives you erl without the standard library.