Предпочтительный вариант: за отделом закреплен 41 человек. Возможный вариант: за отделом закреплено 41 человек (если при формальной роли подлежащего счетный оборот имеет значение обстоятельства меры в страдательной конструкции).

В качестве первого слова в официальном названии правительство пишется с прописной: Правительство Российской Федерации, Правительство Челябинской области. Вне официального названия слово правительство пишется со строчной буквы, как и слова счетный и палата.

Числительные, оканчивающиеся на один, обычно требуют формы единственного числа сказуемого. Однако в некоторых случаях возможна и форма множественного числа. Д. Э. Розенталь приводит такие примеры: 

Двадцать один делегат встретились за круглым столом (сказуемое-глагол встретились указывает на взаимное действие, которое выражается формой множественного числа); 

Двадцать один ящик с посудой, которые были доставлены на базу, попали туда по ошибке (влияние придаточного предложения с союзным словом которые в форме множественного числа); 

За все уплачено 231 рубль (при формальной роли подлежащего счетный оборот имеет значение обстоятельства меры в страдательной конструкции); 

Двадцать один студент не явились на экзамен (эмоционально окрашенный разговорный вариант, подчеркивающий количество отсутствовавших).

Употребление множественного числа при составном числительном, оканчивающемся на один, возможно. Пример с придаточным определительным предложением при таком числительном есть в правилах согласования подлежащего и сказуемого в справочниках Д. Э. Розенталя. 

«При составных числительных, оканчивающихся на один, сказуемое, как правило, ставится в форме единственного числа, например: Двадцать один делегат прибыл на совещание; ...было подано сразу тридцать одно заявление (Шолохов). Форма множественного числа данной конструкции может быть обусловлена контекстом, например: Двадцать один делегат встретились за круглым столом (сказуемое-глагол встретились указывает на взаимное действие, которое выражается формой множественного числа); Двадцать один ящик с посудой, которые были доставлены на базу, попали туда по ошибке (влияние придаточного предложения с союзным словом которые в форме множественного числа); За все уплачено 231 рубль (при формальной роли подлежащего счетный оборот имеет значение обстоятельства меры в страдательной конструкции); Двадцать один студент не явились на экзамен (эмоционально окрашенный разговорный вариант, подчеркивающий количество отсутствовавших)».

Однако лучше предложение перестроить, чтобы избежать грамматической неловкости.

В справочнике Д. Э. Розенталя сказано следующее.

При составных числительных, оканчивающихся на один, сказуемое, как правило, ставится в форме единственного числа, например: Двадцать один делегат прибыл на совещание; …Было подано сразу тридцать одно заявление (Шолохов). Форма множественного числа в данной конструкции возможна по условиям контекста, например: Двадцать один делегат встретились за круглым столом (сказуемое встретились указывает на взаимное действие, которое выражается формой множественного числа); За всё уплачено 92 681 рубль (при формальной роли подлежащего счетный оборот имеет значение обстоятельства меры в страдательной конструкции); Двадцать один студент явились на экзамен (разговорный вариант, влияние тенденции к согласованию по смыслу); Двадцать один ящик с посудой, которые были доставлены на базу, попали туда по ошибке (влияние придаточного предложения с союзным словом которые в форме множественного числа).

Таким образом, верно: 21% уже забронирован. Допустимо: 21% уже забронировано.