Transaction priority is calculated as a value-weighted sum of input age, divided by transaction size in bytes
Fees are a matter of transaction-size and coin-age.
If you received those coins you want to send two weeks (or more) ago and still get that error-message when trying to send them without a fee, i guess you only received fractions of a coin (milli-bitcoins, mBTC).
So when you try to send 0.1BTC now, you need lots of input-transactions to get your output, which blows up your transaction-size.
Add a fee and try again, or wait even longer, you might be able to send them without a fee someday.
Your choice.
Maybe,...just maybe it helps to switch to another electrum-server, i wouldn't count on it though.