The priority doesn't change based on how deep in the queue it is. The priority number is based on a simple formula.
Unless the payment has a decent fee included, priority under 57,600,000 is low priority. The mainline Bitcoin client will prompt you to include a fee in low priority transactions to ensure they are processed, but the .0005 minimum fee is not enough to get most bumped up (although with any fee above that they should be quickly included in a block).https://en.bitcoin.it/wiki/Transaction_fees
"priority = sum(input_value_in_base_units * input_age)/size_in_bytes"
Since when you send coins, the entire address balance is usually sent (with change sent back to you at a new address), this is typical:
priority = ((BTC address balance*100000000) * number of confirmations (weighted over all coins) / size of transaction message in bytes, usually around 300)
For example, send 1 BTC that has been in your wallet for 100 confirmations, in a 300 byte transaction:
100,000,000 * 100 / 300 = priority 33,333,333 = low priority
Priority is only a problem if you send with a 0 fee; see for example the 1VayNert withdraws from the Deepbit mining pool to it's clients: while Deepbit is happy to keep all the transaction fees of blocks they mine for themselves, they don't pay anything back out when sending you a payment, so it may be delayed for hours.