fdisk выдает предупреждение после создания нового раздела

И что он в ответ на это сделает? Мне главное, чтобы данные не потерялись.

только fdisk упорядочивает по всей видимости не по физическому расположению, а по нумерации.

fdisk ничего не упорядочивает, это всего лишь редактор таблицы разделов.

В таблице разделов помещается всего 4 записи о основных разделах.

В начале у вас было создано 3 раздела и было три записи. Затем вы уменьшили второй раздел и изменили вторую запись. После чего на освободившемся пространстве создали раздел, который располагается между 2-м и 3-м разделами, т.е. по факту 3-й раздел, параметры этого раздела была записаны в 4 запись в таблице разделов (partition table).

Физически раздел расположен между 2-м и 3-м разделами, а запись в таблице разделов с его параметрами имеет номер 4.

Об этом вам и говорит fdisk.

В принципе это не страшно, но может внести некоторую путаницу.

Вы можете сами исправить ситуацию, удали 3-ю и 4-ю запись в таблице разделов с описанием разделов и после чего создав в начале третью запись с описанием параметров раздела, расположенного между 2-м и 3-м, а затем записав в 4-ю запись параметры последнего раздела.

Ну либо можете сказать всё это сделать за вас fdisk, смотрите указанные команды.

Ну и что бы посмотреть что сделают указанные команды достаточно набрать:

# fdisk /dev/sdX
x
m

Хорошо, я попробую это сделать. Мне нужно для этого снова загружаться с LiveCD со всеми отмонтированными разделами или можно на загруженной системе сделать?

Лучше на LiveCD.