I believe the problem is the that the # symbol has a special meaning in URIs, so you have to encode it using the Uri.encode()
method like this:
Intent out = new Intent();
out.setAction(Intent.ACTION_DIAL);
out.setData(Uri.parse("tel:" + Uri.encode("+12345#123")));
startActivity(out);