Is solubility a physical change?

Yes.

Really, anything you do to matter that doesn't involve turning it into a different kind of matter (i.e. performing a chemical change) is a physical change.

In the case of dissolving something, think of table salt. When you dissolve table salt in water, it may look different, but it's still good old table salt. Assuming there's no reaction taking place (and there shouldn't be, if you're drinking clean water), dissolving it leaves it as good old NaCl.

OK.