Now changing priority takes too much time,
especially when you have a lot of tasks.

Maybe drag and drop priority changing would be good.
Maybe just a context menu with priorities would be enough.

See also other topic about prioritizing:

Drag and drop to reorder tasks:
http://www.rememberthemilk.com/forums/ideas/3154/