The test failure is on the Windows build, and unrelated

WARNING: The following packages cannot be authenticated!
  liblcms2-2 liblcms2-2 wine1.7-amd64 wine1.7-i386 wine1.7
E: There are problems and -y was used without --force-yes
The command "sudo apt-get install --no-install-recommends --no-upgrade -qq nsis gcc-mingw-w64-x86-64 g++-mingw-w64-x86-64 binutils-mingw-w64-x86-64 mingw-w64-dev wine1.7 bc" failed. Retrying, 3 of 3.

hmm, i'd suggest that perhaps MIN_CHANGE could depend on the input amounts?
otherwise it seems like this might be too drastic a change.

The tests assume that the minimum change is static, so they'd need to be adjusted as well if the minimum change now depends on the target value.

The current MIN_CHANGE is 1000000 bits (0.01 BTC) and I agree that this is relatively high.
This change would reduce the static MIN_CHANGE to 1000 bits (0.00001) which is to low IMO and might result in dust/uneconomic inputs.

Also I'm not sure if coupling it with DEFAULT_TRANSACTION_MINFEE (or other fee relevant vars) is the right thing, because it's unknown when the change output will be used as input (1-2 years)?

I tend to keep the value high to prevent from creating dusty outputs (assume fees are rising).
But maybe I'm looking at it from the wrong perspective. So correct me if i'm wrong.
Tend to NACK.

I created this pull to see what other opinions exist.

Basically, changing the defaults to work around bugs is not the right way. Instead the wallet code should select coins more intelligent to prevent large transactions and also prevent combining inputs from many different addresses.

A one-line adjustment for 0.12 with something like CENT/10 could make sense in the short term, though.

I plan to address the wallet code changes until 0.13 or 0.14.

[...] A one-line adjustment for 0.12 with something like CENT/10

Agree. But not sure about 0.12. Rc1 is already out and we might want to keep the existing MIN_CHANGE behavior in 0.12.

I will think about this and open a new pull next week.